[NOIP 2024 模拟1]zyc不能大吃特吃

[NOIP 2024 模拟1]zyc不能大吃特吃

题意

给出两个序列 \(a,b\)，给出两个数 \(A,B\)。

求最少选出多少个数，使得刚好不满足 \(\sum a_i\le A\) 且 \(\sum b_i\le B\)。

思路

贪心，\(A\) 和 \(B\) 有一个超出即可。

将序列分别按 \(a\) 和 \(b\) 排序，看那个能选的最少。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, A, B;
struct dish {int a, b;};
dish x[N];
bool cmpa(dish X, dish Y) {
	return X.a > Y.a;
}
bool cmpb(dish X, dish Y) {
	return X.b > Y.b;
}
void solve() {
	cin >> n >> A >> B;
	for (int i = 1; i <= n; i ++) cin >> x[i].a >> x[i].b;
	sort(x + 1, x + n + 1, cmpa);
	int a = 0, b = 0, ans1 = 0;
	for (int i = 1; i <= n; i ++) {
		a += x[i].a, b += x[i].b, ans1 ++;
		if (a > A || b > B) break;
	}
	sort(x + 1, x + n + 1, cmpb);
	a = 0, b = 0; int ans2 = 0;
	for (int i = 1; i <= n; i ++) {
		a += x[i].a, b += x[i].b, ans2 ++;
		if (a > A || b > B) break;
	}
	cout << min(ans1, ans2) << "\n";
}
signed main() {
	freopen("no.in", "r", stdin);
	freopen("no.out", "w", stdout);
	int Case = 1;
//	cin >> Case;
	while (Case --)
		solve();
	return 0;
}