P3545

· · 题解

题面

题意

题目中给出两个数组 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;
}