反悔贪心
P3045 [USACO12FEB] Cow Coupons G
题目背景
Subtask 0 为原数据，Subtask 1 为 hack 数据。
题目描述
Farmer John needs new cows! There are N cows for sale (1 <= N <= 50,000), and FJ has to spend no more than his budget of M units of money (1 <= M <= 10^14). Cow i costs P_i money (1 <= P_i <= 10^9), but FJ has K coupons (1 <= K <= N), and when he uses a coupon on cow i, the cow costs C_i instead (1 <= C_i <= P_i). FJ can only use one coupon per cow, of course.
What is the maximum number of cows FJ can afford?
FJ 准备买一些新奶牛。市场上有 \(N\) 头奶牛，第 \(i\) 头奶牛价格为 \(P_i\)。FJ 有 \(K\) 张优惠券，使用优惠券购买第 \(i\) 头奶牛时价格会降为 \(C_i\)，当然每头奶牛只能使用一次优惠券。FJ 想知道花不超过 \(M\) 的钱最多可以买多少奶牛？
- \(1 \le K \le N \le 5 \times 10^4\)
- \(1 \le C_i \le P_i \le 10^9\)
- \(1 \le M \le 10^{14}\)
输入格式
* Line 1: Three space-separated integers: N, K, and M.
* Lines 2..N+1: Line i+1 contains two integers: P_i and C_i.
输出格式
* Line 1: A single integer, the maximum number of cows FJ can afford.
样例 #1
样例输入 #1
4 1 7
3 2
2 2
8 1
4 3
样例输出 #1
3
提示
FJ has 4 cows, 1 coupon, and a budget of 7.
FJ uses the coupon on cow 3 and buys cows 1, 2, and 3, for a total cost of 3 + 2 + 1 = 6.**
题目分析
这题一眼 \(01\) 背包，但是
\(1 \le K \le N \le 5 \times 10^4\)
\(1 \le M \le 10^{14}\)
显然不行，所以考虑贪心：
贪心本身是没有反悔操作的，贪心求的就是当前的最优解。但当前的最优解有可能是局部最优解，而不是全局最优解，这时候就要进行反悔操作。
众所周知，正常的贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。也就是说我们的每一步都是站在当前产生的局面上所作出的最好的选择，是没有反悔操作的。
不加反悔的一直朝着当前局面的最优解走很可能导致我们被困在局部的最优解而无法到达全局的最优解，就好像我们爬山就只爬到了一座山的山顶却没有到整片山的最高处：
但是反悔贪心允许我们在发现现在不是全局最优解的情况下回退一步或若干步采取另外的策略去取得全局最优解。就好像我们站在的一座山的山峰上，看到了还有比我们现在所在位置还高的山峰，那我们现在就肯定不是在最高的地方了，这时我们就反悔——也就是下山再爬上那座更高的山：
这就是反悔贪心的大致思路。根据反悔记录操作的不同，反悔贪心又分为反悔堆和反悔自动机。
以上来自 dalao
很直接的想法是将所有牛按 \(c\) 值排序买 \(k\) 个 \(c\) 值最小的，然后剩下的钱原价买。
所有钱只够买这前\(k\)只的情况很显然都用优惠券买
以下考虑有剩余的钱买 \(k+1\) 到 \(n\) 的牛
- 这 \(k\) 个 \(c\) 值最小的一定会被买
反证法：如果有一种方案是这k只牛中有一只（ \(A\) ）不买而是买其他的（ \(B\) ），若 \(A\) 替换 \(B\) 来用优惠券，花的钱一定会更少，方案会更优，所以先将这k只牛用优惠券买了。
再考虑调整：
- 这 \(k\) 个 \(c\) 值最小的又不一定会用优惠券
这 \(k\) 个牛中所用的优惠券如果用在后面原价买的牛身上会使当前决策更优，
即 \(c_x+p_y > p_x+c_y\) (\(1 \le x \le k\)，\(k+1 \le y \le n\))
这时可以将这个优惠券转移，则这只牛买来的费用为 \(p_x-c_x+c_y\)
当然如果存在用原价买比用上面这种方式买更优那就直接用原价买。
代码实现
开三个小根堆：
-
前 \(k\) 只奶牛的 \(P\) 值与 \(C\) 值之差。
-
第 \(k + 1\) 到第 \(n\) 只奶牛的 \(C\) 值。
-
第 \(k + 1\) 到第 \(n\) 只奶牛的 \(P\) 值。
先按 \(c\) 值排序，
将前 \(k\) 只奶牛的 \(P\) 值与 \(C\) 值之差存入\(1\)堆，
将第 \(k + 1\) 到第 \(n\) 只奶牛的 \(C\) , \(P\) 值分别存入 \(2\) , \(3\) 堆，
每次按上面两种策略的最优策略买牛直到钱不够。
std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 5e4+9;
int n,k;
ll m;
PII a[N];
bool vis[N];
ll sum;
int cnt;
priority_queue<int,vector<int>,greater<int> > d;//原价与优惠价的差值
priority_queue<PII,vector<PII>,greater<PII> > p,c;
int main()
{
scanf("%d%d%lld",&n,&k,&m);
for(int i = 1;i <= n;i++)scanf("%d%d",&a[i].second,&a[i].first);//sort排序pair<int,int>默认按first排
sort(a+1,a+1+n);
for(int i = 1;i <= k;i++)
{
int t = a[i].second-a[i].first;
d.push(t);
sum += a[i].first;
if(sum > m)printf("%d",i-1),exit(0);
}
if(sum > m)printf("%d",k-1),exit(0);
cnt = k;
for(int i = k+1;i <= n;i++)p.push({a[i].second,i}),c.push({a[i].first,i});
while(sum < m)
{
//访问堆之前最好先判空
while(!p.empty() && vis[p.top().second])p.pop();//已经买过的牛就不用再参与了
while(!c.empty() && vis[c.top().second])c.pop();
if(c.empty() || p.empty())break;//买完了所有牛
PII tp = p.top(),tc = c.top();
int td = d.top();//减少访问堆的次数节省时间
if(tp.first < tc.first + td)
{
if(sum + tp.first <= m)
{
cnt++;
sum += tp.first;
vis[tp.second] = 1;
p.pop();
}
else break;//没钱了最便宜的都没不了
}
else if(!d.empty())//判断还有没有优惠券
{
if(sum + tc.first + td <= m)
{
cnt++;
sum += tc.first + td;
vis[tc.second] = 1;
c.pop(),d.pop();
d.push(a[tc.second].second-a[tc.second].first);
//当前的决策只是局部最优之后优惠券还可能转移
//所以要将新的差值加入堆
}
else break;//没钱了
}
else //没优惠券了但还有钱，一直按原价买
{
while(!p.empty() && sum + p.top().first <= m)cnt++,sum += p.top().first,p.pop();
break;
}
}
printf("%d",cnt);
return 0;
}
//--------AC7