[POI 2012] HUR-Warehouse Store题解

1.题目

现在有 $n$ 天。第 $i$ 天上午会进货 $a_i$ 件商品，中午的时候会有顾客需要购买$b_i$件商品，可以选择满足顾客的要求，或是无视掉他。

如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足多少个顾客的需求。

2. 思路

这道题是一道比较经典的反悔贪心（我竟然没有一下切出来，我太废了）

首先，每天都需要进货（我竟然在这里调了半天）

接下来，考虑贪心，把能满足条件的顾客尽量满足了。

但问题是，在满足顾客条件时有可能怎么也满足不了了（也就是当前所剩的库存，怎么也无法让第$i$个顾客拿走$b_i$个货物了）。

这时，我们需要反悔 操作：

为了方便，先设第$i$天来的顾客无法在当前情况下被满足（库存完全不够了）

在每次反悔时，我们希望把消耗商品件数（$b_i$）最多 的顾客给替换为当前的顾客$i$

于是，我们可以使用一个大根堆 来维护已经加入 的顾客中消耗商品最多 的

每次加入与反悔时动态维护当前有的商品数就行

这道题我们就做完了

小细节，这道题还需要输出天数编号，只需要在优先队列里存个$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;
}