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; }