社区讨论
还差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 条回复,欢迎继续交流。
正在加载回复...