Codeforces 222 D. Olympiad

問題

n人が参加した大会がある。
大会は2種目の得点の合計が多い人が良い順位になり、
同点の場合は、同点の間でどの順位にもなる可能性がある。


1番目の種目と2番目の種目の得点が順不同で与えられる。
自分はこの中のどれかで、合計がx点以上であることがわかっている。


このとき、自分の取りうる最高の順位と、最低の順位をそれぞれ出力せよ。

制約条件

n≦10^5
x≦2 * 10^5

方針

取りうる最高の順位は自明に1.
最低の順位は、
1番目の種目と2番目の種目の得点を適当に組み合わせて、
なるべく多くのx点以上の人を作る。このとき、作れた人数をa個とすると、
a位が最低の順位になる。


なので、この2部グラフの最大マッチングを高速に求められればよい。
1番目の種目の点数を決めると、
2番目の種目は、まだ使ってない点数の中で、x点になるもののうち最も点数の低いものを貪欲に使えばよい。


なので、これは尺取法を使えばO(n)で求まる。

ソースコード

int n, x, a[100000], b[100000];


int main(){
	cin >> n >> x;
	rep(i, n) cin >> a[i];
	rep(i, n) cin >> b[i];
	
	sort(a, a + n);
	sort(b, b + n);
	
	int a1 = 0, j = 0;
	for(int i = n - 1; i >= 0; i--){
		while(j < n - 1 && a[i] + b[j] < x) j++;
		if(j < n && a[i] + b[j] >= x) a1++, j++;
	}
	cout << 1 << " " << a1 << endl;
	
	return 0;
}