提交记录

大概是先按照原价从小到大排序，去所有能取的，然后把剩余的按照用优惠券后的价格从小到大排序，接着进行 k 次操作，如果满足当前价格加上未选取的物品中用过优惠券后最小的价格小于 m ，就把次物品选取，否则比较当前已经选取的物品中最大值和未选取的最小值，如果大于，就交换两个物品的位置，否则直接退出

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e6+10;

int n,k,m;
int p[N],c[N];
priority_queue<pair<int,int>,vector<pair<int,int> > ,greater<pair<int,int> > > q,out;
priority_queue<pair<int,int> > due;

signed main(){
	scanf("%lld%lld%lld",&n,&k,&m);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i],&c[i]),q.push(make_pair(p[i],c[i]));
	int sum=0;
	while(sum<=m && q.size()){
		if(sum+q.top().first<=m) 
			due.push(q.top()),sum+=q.top().first,q.pop();
		else break ;
	}
	if(!q.size()) return printf("%lld",n),0;
	while(q.size()) 
		out.push(make_pair(q.top().second,q.top().first)),q.pop();
	for(int i=1;i<=k;i++){
		if(sum+out.top().first<=m) 
			due.push(out.top()),sum+=out.top().first,out.pop();
		else if(sum-due.top().first+due.top().first<=m){
			pair<int,int> due_out=due.top(),out_out=out.top();
			due.pop(),out.pop();
			sum=sum-due_out.first+out_out.first,due.push(out_out),out.push(make_pair(due_out.second,due_out.first));
		}else break ;
	}
	printf("%lld",due.size());
	return 0;
}