思路
首先,\(k\) 张优惠券肯定是全部要用的,我们只需要考虑怎么分配即可。
不难发现,将 \(C\) 数组升序排序后,前 \(k\) 个必然在答案之中,但不一定要使用优惠券,可以用反证法证明。
按照贪心的套路,可以先将前 \(k\) 个 \(C_i\) 扔进一个堆里,后期再一步一步更新。
考虑 \(i \gt k\) 的情况:
-
当不使用优惠券时,贪心地选择使得 \(P_i\) 最小的 \(i\)
-
当使用优惠券时,前面的已经使用过优惠券的一个 \(j\) 必然要做出让步,票价总和会累加上 \(C_i + P_j - C_j\)
对于第一种情况,我们可以用一个堆选出 \(P\) 值最小的 \(i\) 。
对于第二种情况,拆成 \(C_i\) 和 \(P_j-C_j\) 两部分,分别选出使其最小的 \(i\) 和 \(j\) 即可。
那么最终比较一下两种情况的票价,选较小者累加,总共使用三个优先队列。
CODE
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n,k;
ll m;
ll c[maxn],p[maxn];
struct node {
ll x,y;
int id;
node() {
x = y = id = 0;
}
node(ll x,ll y,int id):x(x),y(y),id(id){}
}a[maxn];
struct cmp_P {
bool operator()(const node& p,const node& q) {
return p.x > q.x;
}
};
struct cmp_C {
bool operator()(const node& p,const node& q) {
return p.y > q.y;
}
};
struct cmp_Diff {
bool operator()(const node& p,const node& q) {
return p.x - p.y > q.x - q.y;
}
};
priority_queue <node,vector<node>,cmp_P > P;
priority_queue <node,vector<node>,cmp_C > C;
priority_queue <node,vector<node>,cmp_Diff > Diff;
bool vis[maxn];
int main() {
scanf("%d%d%lld",&n,&k,&m);
for(int i = 1;i <= n;++ i) {
scanf("%lld %lld",&p[i],&c[i]);
a[i] = node(p[i] , c[i] , i);
P.push(a[i]);
C.push(a[i]);
}
int ans = 0;
for(int i = 1;i <= k;++ i) {
node u = C.top();
C.pop();
m -= u.y;
if(m < 0) {
printf("%d",ans);
return 0;
}
++ ans;
vis[u.id] = true;
Diff.push(u);
}
for(int i = k + 1;i <= n;++ i) {
while(vis[C.top().id])C.pop();
while(vis[P.top().id])P.pop();
node p = C.top(),q = Diff.top(),u = P.top();
if(q.x - q.y + p.y <= u.x) {
m -= q.x - q.y + p.y;
if(m < 0) {
printf("%d",ans);
return 0;
}
++ ans;
C.pop();
Diff.pop();
Diff.push(p);
vis[q.id] = true;
}
else {
m -= u.x;
if(m < 0) {
printf("%d",ans);
return 0;
}
++ ans;
vis[u.id] = true;
P.pop();
}
}
printf("%d",n);
return 0;
}