如果你的反悔贪心类似于这样:
int n, k; ll m, tot = 0; int cnt = 0; pii s[N];
std::priority_queue<ll, std::vector<ll>, std::greater<ll> > q;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
std::cin >> n >> k >> m;
for(int i = 1; i <= n; ++i) std::cin >> s[i].p >> s[i].c;
std::sort(s + 1, s + n + 1, [&](pii a, pii b) { return (a.c ^ b.c) ? a.c < b.c : a.p < b.p; });
for(int i = 1; i <= n; ++i) {
int d = s[i].p - s[i].c; ll ad = 0;
if((int)q.size() < k) ad = s[i].c, q.push(d);
else if(!q.empty() && q.top() < d) ad = q.top() + s[i].c, q.pop(), q.push(d);
else ad = s[i].p;
if(tot + ad > m) break; tot += ad, ++cnt;
}
std::cout << cnt;
return 0;
}
那么是不对的,原因在于你不应该直接用排序的顺序去选牛。正确的方法见题解,要用三个堆动态地去选。