题意

有$n$个物品，每个物品有一个原价和一个会员价

我们可以使用$k$次会员价

问当你有$m$元钱的时候最多能买多少商品

$1<=n<=5e4$

$0 <= k <= n$

$1 <= b[i] <= a[i] <= 1e9$

$1 <= m <= 10e14$

做法

反悔贪心

我们每次选择原价最小或者使用完优惠券最小的商品

设用优惠券的钱为$c$,原价为$p$

若满足

$c_j + (p_i - c_i) < p_k$

($c_j$指最便宜的优惠价，$(p_i-c_i)$指优惠最少的优惠券省下的钱，$p_k$指最便宜的原价)

就将优惠券转移

否则就加最小的原价

code

#include <bits/stdc++.h>
using namespace std;

const long long N = 5e4 + 10;

long long n, k, m, c[N], p[N];

void read(){
	cin >> n >> k >> m;
	for(long long i = 1;i <= n; i++){
		cin >> p[i] >> c[i];
	}
	return ;
}

priority_queue<long long,vector<long long>,greater<long long> > d;

struct node{
	long long val, id;
	friend bool operator < (node a,node b){
		return a.val > b.val;
	}
};

priority_queue<node> P, C;

bitset<N> vis;

void compute(){
	for(long long i = 1;i <= n; i++){
		P.push({p[i],i});
		C.push({c[i],i});
	}
	for(long long i = 1;i <= k; i++){
		d.push(0);
	}
	long long ans = 0, sum = 0;
	while(P.size()){
		node a = P.top();
		node b = C.top();
		if(vis[a.id]) {
			P.pop();
			continue;
		}
		if(vis[b.id]){
			C.pop();
			continue;
		}
		if(a.val < b.val + d.top()){
			sum += a.val;
			if(sum > m) break;
			ans++;
			P.pop();
			vis[a.id] = 1;
		}
		else{
			sum += b.val + d.top();
			if(sum > m) break;
			ans++;
			C.pop();
			vis[b.id] = 1;
			d.pop();
			d.push(p[b.id]-c[b.id]);
		}
	}
	cout << ans;
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	read(); compute();
	return 0;
}

我们首先可以想到无法一次贪心求出

所以我们考虑反悔贪心

我们设当前用优惠券花的钱为 $k$ 并且考虑用 $i$ 替换掉 $j$

那么有

移项得

那么我们可以用一个优先队列维护 $p_i-c_i$ 然后求出最小值