社区讨论

还差4个点AC

P3045[USACO12FEB] Cow Coupons G参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mhj43yux
此快照首次捕获于
2025/11/03 20:24
4 个月前
此快照最后确认于
2025/11/03 20:24
4 个月前
查看原帖
求救
CPP
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define int __int128
#define int unsigned long long
#define pii pair <int, int>
#define x first
#define y second
const int N = 5e4 + 10;
inline int read () { // 快读模板
	int x = 0, f = 1;
	char ch = getchar ();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar ();}
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar ();}
	return x * f;
}
inline int pow_2 (int x) {return pow (2, x);}
struct ZZZ {
	int p, c, wz, q;
} x[N];
bool cmp (ZZZ X, ZZZ Y) {
	return X.q > Y.q;
}
bool cnp (ZZZ X, ZZZ Y) {
	return X.q < Y.q;
}
bool cmpp (ZZZ X, ZZZ Y) {
	return X.p < Y.p;
}
void solve () {
	int n, k, m; cin >> n >> k >> m;
	for (int i = 1; i <= n; i++) {
		cin >> x[i].p >> x[i].c, x[i].wz = i, x[i].q = x[i].p - x[i].c;
	}
	sort (x + 1, x + 1 + n, cmp);
	int ans = 0, cnt = 0, z = INT_MAX;
	vector <bool> vis(n + 1, false);
	for (int i = 1; i <= k; i++) {
		if (vis[x[i].wz]) continue;
		if (cnt + x[i].c > m) break;
		cnt += x[i].c, ++ ans, vis[x[i].wz] = true;
	}
	sort (x + 1, x + 1 + n, cmpp);
	for (int i = 1; i <= n; i++) {
		if (vis[x[i].wz]) continue;
		if (cnt + x[i].p > m) break;
		cnt += x[i].p;
		++ ans;
		vis[x[i].wz] = true;
	}
	z = ans, ans = 0, cnt = 0;
	for (int i = 1; i <= n; i++) {
		x[i].q = x[i].c;
	}
	sort (x + 1, x + 1 + n, cnp);
	vector <bool> v(n + 1, false);
	for (int i = 1; i <= k; i++) {
		if (v[x[i].wz]) continue;
		if (cnt + x[i].c > m) break;
		cnt += x[i].c, ++ ans, v[x[i].wz] = true;
	}
	sort (x + 1, x + 1 + n, cmpp);
	for (int i = 1; i <= n; i++) {
		if (v[x[i].wz]) continue;
		if (cnt + x[i].p > m) break;
		cnt += x[i].p;
		++ ans;
		v[x[i].wz] = true;
	}
	cout << max (z, ans) << "\n";
}
signed main () {
	ios::sync_with_stdio (false);
	cin.tie (NULL);
	cout.tie (NULL);
    int T = 1; // T = read ();
	while (T--) {solve ();}
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...