「BZOJ2802」[POI2012] Warehouse Store
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
每一天的a[i]可以用来满足这一天包括之后的b[i]
那么只要倒序处理这个问题，每一天的a[i]用于满足这一天之后最小的b[i]即可
用堆维护最小值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include<map> #include<set> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #define inf 1000000000 #define pa pair<int,int> using namespace std; int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,ans,top; int a[250005],b[250005]; bool dis[250005]; priority_queue<pa,vector<pa>,greater<pa> >q; int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) b[i]=read(); for(int i=n;i;i--) { q.push(make_pair(b[i],i)); while(a[i]&&!q.empty()) { int t=q.top().first,id=q.top().second; q.pop(); int mn=min(t,a[i]); t-=mn;a[i]-=mn; if(t)q.push(make_pair(t,id)); else ans++; } } printf("%d\n",ans); while(!q.empty()) { dis[q.top().second]=1; q.pop(); } for(int i=1;i<=n;i++) if(!dis[i])printf("%d ",i); return 0; } |
Subscribe
计数器 9787185
OI 课件=>
OI 课件=>