2802: [Poi2012]Warehouse Store
Time Limit: 10 Sec Memory Limit: 64 MBSec Special Judge
Submit: 231 Solved: 119
[Submit][Status][Discuss]
Description
有一家专卖一种商品的店，考虑连续的n天。
第i天上午会进货Ai件商品，中午的时候会有顾客需要购买Bi件商品，可以选择满足顾客的要求，或是无视掉他。
如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足多少个顾客的需求。
Input
第一行一个正整数n (n<=250,000)。
第二行n个整数A1,A2,...An (0<=Ai<=10^9)。
第三行n个整数B1,B2,...Bn (0<=Bi<=10^9)。
Output
第一行一个正整数k，表示最多能满足k个顾客的需求。
第二行k个依次递增的正整数X1,X2,...,Xk，表示在第X1,X2,...,Xk天分别满足顾客的需求。
Sample Input
6
2 2 1 2 1 0
1 2 2 3 4 4
2 2 1 2 1 0
1 2 2 3 4 4
Sample Output
3
1 2 4
1 2 4
HINT
Source
贪心题。。。因为题目要求是满足要求的人数最多而不是收获价值最多。。所以我们先对于每一天判断当前的剩余是否足够。。如果足够就满足顾客要求。。如果不够就去之前的时间中找到需求最多的一天然后替换。。这样满足要求的人数不变但是库存增加了。。
然后找最大可以用堆维护。。。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define ll long long
using namespace std;
const ll N = 250010;
struct data{ll val,id;} t;
bool operator < (data a,data b){return a.val<b.val;}
priority_queue <data> heap;
ll n,a[N],b[N],now,ans[N],tot;
ll read(){
ll x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
int main(){
n = read();
for (ll i=1;i<=n;i++) a[i] = read();
for (ll i=1;i<=n;i++) b[i] = read();
for (ll i=1;i<=n;i++){
now+=a[i];
if (now>=b[i]) {
now-=b[i];heap.push((data){b[i],i});
ans[i] = 1;
}
else if (!heap.empty()){
t = heap.top();
if (t.val>b[i]) heap.pop(),ans[t.id] = 0,ans[i] = 1,now+=t.val-b[i],heap.push((data){b[i],i});
}
}
for (ll i=1;i<=n;i++) if (ans[i]) tot++;
printf("%d\n",tot);
for (ll i=1;i<=n;i++) if (ans[i]) printf("%d ",i);
}
评论 (0)
