自动搬运

查看原文

来自洛谷，原作者为

	Macesuted AFOed

搬运于2025-08-24 21:50:03，当前版本为作者最后更新于2020-08-16 17:21:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面

题意

题目中给出两个数组 $A[]$ 和 $B[]$ ，你拥有一个存货数量，在第 $i$ 天的上午会加上 $A_i$ ，下午你可以选择减少 $B_i$ 的存货来满足一个顾客的要求。问 $n$ 天内你最多能满足多少顾客。

做法

我们先尽可能满足所有我们遇到的顾客，并且使用一个大根堆存放所有你当前满足过的顾客的信息。当我们遇到一个我们无法直接满足的顾客，如果大根堆的堆顶的 $B_i$ 小于当前的 $B_i$ ，我们尝试取出大根堆的堆顶，将它删除并且将它的 $B_i$ 加入你的存货数量中，然后你继续满足这一位顾客。

算法正确性证明

由于我们前提条件中有“大根堆堆顶的 $B_i$ 大于当前的 $B_i$ ”，如果我们不满足大根堆堆顶的顾客（即当前方案下所有我们满足的顾客中 $B_i$ 最大的），我们一定是能够用取消堆顶的顾客所拿来的库存来满足当前顾客的，所以我们满足的顾客数量不降，并且你手头上的存货数量还有可能上升，也对答案有正面影响。所以不满足堆顶，满足当前项在这样的情况下是满足贪心的局部最优的。

代码

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

const int maxn=250005;

typedef pair<long long,int> pii;

long long a[maxn],b[maxn];
bool vis[maxn];//记录是否满足每一位顾客

priority_queue<pii,vector<pii>,less<pii> > que;

int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",a+i);
	for(int i=1;i<=n;i++) scanf("%lld",b+i);
	long long tot=0,cnt=0;
	for(int i=1;i<=n;i++)
	{
		tot+=a[i];
		if(tot<b[i]&&!que.empty()&&que.top().first>b[i])
		{//若无法满足当前顾客并且堆顶更贵的情况
			vis[que.top().second]=false;
			tot+=que.top().first;//删除堆顶
			que.pop();
			cnt--;
		}
		if(tot>=b[i])
		{
			tot-=b[i];
			que.push((pii){b[i],i});
			vis[i]=true;//加入当前点
			cnt++;
		}
	}
	printf("%lld\n",cnt);
	for(int i=1;i<=n;i++)
		if(vis[i]) printf("%d ",i);
	puts("");
	return 0;
}