题解 P3545 【[POI2012]HUR-Warehouse Store】

小手冰凉 · 2017-09-19 18:52:30 · 题解

这题的做法是贪心

很明显可以发现，当能卖时就卖是一个十分好的贪心策略

但是会有一种情况例外，就是前面有一个很大的人要买，以至于后面的一群人都不能买了

所以可以用堆维护一下在之前买的人最大是多少，如果当前的人买不了，而堆中最大比当前大就把那个人换成现在这个，如果现在的最大比之前还大显然换了更加不优。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=250005;
int n;
int a[N],b[N];
struct xxx{
    int k,t;
}heap[N];
bool com(xxx a,xxx b)
{
    return a.t<b.t;
}
bool comm(xxx a,xxx b)
{
    return a.k<b.k;
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    int t=0;
    int k=0;
    memset(heap,0,sizeof(heap));
    make_heap(heap+1,heap+t+1,com);
    for(int i=1;i<=n;i++){
//        cout<<heap[1].t<<' '<<heap[1].k<<endl;
        k+=b[i];
        if(a[i]<=k){//贪心
            k-=a[i];
            t++;
            heap[t].t=a[i];
            heap[t].k=i;
            push_heap(heap+1,heap+t+1,com);
        }
        else if(heap[1].t>=a[i]){//用堆维护，将之前的解改的更优
            k+=heap[1].t;
            k-=a[i];
            pop_heap(heap+1,heap+t+1,com);
            heap[t].t=a[i];
            heap[t].k=i;
            push_heap(heap+1,heap+t+1,com);
        }
    }
    sort(heap+1,heap+t+1,comm);
    printf("%d\n",t);
    for(int i=1;i<=t;i++){
        printf("%d ",heap[i].k);
    }
    return 0;
}