Codeforces Round #137 (Div. 2) D : Olympiad

問題概要

長さN(<10^5)の数列A,Bが与えられる。A,Bを適当に置換してC[i]=A[i]+B[i]とする。このとき、CのうちX以上のものが最大いくつ作れるか求める問題。

解法

Aを降順にソートして、BからA[i]+B[j]>=Xなる最小のjを求める。しゃくとりっぽくやってもよいけど、どうせソートでO(N*log N)なので二分探索でよい。

acceptされたコード

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

const int MAX_N = int(1e5);
int N, X;
int as[MAX_N], bs[MAX_N];

void init() {
	scanf("%d%d", &N, &X);
	for (int i = 0; i < N; ++i) {
		scanf("%d", as + i);
	}
	for (int i = 0; i < N; ++i) {
		scanf("%d", bs + i);
	}
}

int solve() {
	sort(as, as+N, greater<int>());
	multiset<int> nums(bs, bs+N);

	for (int i = 0; i < N; ++i) {
		multiset<int>::iterator itr = nums.lower_bound(X - as[i]);
		if (itr == nums.end()) {
			return i;
		}
		nums.erase(itr);
	}
	return N;
}

int main() {
	init();
	printf("1 %d\n", solve());
	return 0;
}