[BZOJ2802][Poi2012]Warehouse Store 堆の贪心



贪心,每天能卖货就卖出去,不能卖则找出之前最大的一笔单子,如果比今天的小就买回来卖给今天这人.使用堆来实现.
原谅我智商感人不知道pair<int,int>默认先按第一关键字排序 调了一晚上哭着

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 255555
#define mp make_pair
using namespace std;
typedef pair<int,int> par;
int n,a[N],b[N],ans;
bool v[N];
priority_queue<par>q;
inline void read(int &x)
{
    x=0;char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c<='9'&&c>='0')x=(x<<1)+(x<<3)+c-'0',c=getchar();
}
long long now;
int main()
{
    // freopen("data.in","r",stdin);
    // freopen("my.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)read(a[i]);
    for(int i=1;i<=n;i++)read(b[i]);
    for(int i=1;i<=n;i++)
    {
        now+=a[i];
        if(now>=b[i])
        {
            ans++;v[i]=1;
            now-=b[i];
            q.push(mp(b[i],i));
        }
        else if(!q.empty()&&q.top().first>=b[i])
        {
            now+=q.top().first;v[q.top().second]=0;
            now-=b[i];v[i]=1;
            q.pop();q.push(mp(b[i],i));
        }
    }
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)if(v[i])printf("%d ",i);
    // fclose(stdin);
    // fclose(stdout);
    return 0;
}
/*
20
76 3 6 26 45 41 48 31 15 52 1 74 11 11 19 66 26 75 1 19 
7 2 97 89 46 24 89 81 64 84 40 11 28 41 19 72 84 44 78 87 
*/

发表评论

电子邮件地址不会被公开。 必填项已用*标注