--->传送门

题目大意

在 $n(1 \le n \le 250000)$ 天中，给你每天商品的进货量和每天可能的出货量，求出最多能满足多少天的可能的出货量和对应的时间，商品可以累积

思路

一眼贪心

先建一个大根堆用来存可能的商品出货量和对应的时间，正序枚举天数。

对于第 $i$ 天，首先先考虑当前货物是否能满足当前可能的出货量的需求：如果满足就可以直接进堆，不满足的话就将当前可能的出货量与堆顶作比较，贪心的将较小的可能的出货量加入堆，再将大的踢出来，以便以后能更好的满足其他天数的出货量

代码中有详细的注释

代码

#include<bits/stdc++.h>
#define in inline
#define ri register
#define int long long int 
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
in void write(int x)
{
    if(x<0) {x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int maxn=250001;
int awa[maxn];//用来存每天的进货量
bool vis[maxn];//标记能满足哪天的出货量
priority_queue<pair<int,int> > q;//大根堆，用 pair 存第 i 天的出货量
signed main()
{
    cin.tie(NULL);cout.tie(NULL);
    int n=read(),sum=0;
    for(ri int i=1;i<=n;i++) awa[i]=read();
    for(ri int i=1;i<=n;i++)
    {
        sum+=awa[i];//当前库存的货物
        int x=read();
        if(sum>=x) q.push(make_pair(x,i)),vis[i]=1,sum-=x;//如果满足就可以直接进堆
        else
        {
            if(q.empty()) continue;//这里得判断一下，可能当前库存比要求出货量小，并且堆为空，这时直接弃掉当天的选择
            if(q.top().first>x)//堆顶比第 i 天出货量大，让小的进堆，大的出堆
            {
                vis[q.top().second]=0;//之前的商品不出了，标成0
                vis[i]=1;//出当前的商品，标为1
                sum+=q.top().first,sum-=x;//别忘了更新一下当前的库存商品
                q.pop();q.push(make_pair(x,i));
            }
        }
    }
    write(q.size()),puts("");//现在堆的大小就是能出商品的最大天数
    for(ri int i=1;i<=n;i++) if(vis[i]) cout<<i<<" ";//依次将标记的天数输出出来
    return _123hh2;
}