[POI 2012] HUR-Warehouse Store题解
1.题目
现在有 \(n\) 天。第 \(i\) 天上午会进货 \(a_i\) 件商品，中午的时候会有顾客需要购买\(b_i\)件商品，可以选择满足顾客的要求，或是无视掉他。
如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足多少个顾客的需求。
2. 思路
这道题是一道比较经典的反悔贪心（我竟然没有一下切出来，我太废了）
首先，每天都需要进货（我竟然在这里调了半天）
接下来，考虑贪心，把满足的顾客全部满足了。
但问题是，可能到了某一次时无法满足顾客的条件了。
这时，我们需要反悔操作：
在每次反悔时，我们希望把消耗商品件数最多的顾客给替换为当前这个塞不下的顾客
于是，我们可以使用一个大根堆来维护已经加入的顾客中消耗商品最多的
每次加入与反悔时动态维护当前有的商品数就行
这道题我们就做完了
小细节，这道题还需要输出天数编号，只需要在优先队列里存个\(pair<消耗商品件数b_i,第几天>\)
3.Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[2000010],b[2000010];main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];priority_queue<pair<int,int> >q;int now=0;for(int i=1;i<=n;i++){now+=a[i];if(now>=b[i]){q.push({b[i],i});now-=b[i];}else if(q.size() and b[i]<=q.top().first){now-=b[i];now+=q.top().first;q.pop();q.push({b[i],i});}}cout<<q.size()<<'\n';while(q.size())cout<<q.top().second<<' ',q.pop();return 0;
}