有一家专卖一种商品的店，考虑连续的n天。
第i天上午会进货Ai件商品，中午的时候会有顾客需要购买Bi件商品，可以选择满足顾客的要求，或是无视掉他。
如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足多少个顾客的需求。
2802: [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
Sample Output
3
1 2 4
HINT
Source
【分析】
可爱的贪心题。
【并没有秒，并且表示想了很久，并且表示样例调了挺久】
【幸好1A】【好吧学不会大颓果的来者不拒思想ORZ】
先说我的方法：
每次选最小的bi取，然后库存减掉，树状数组维护前缀和。
减库存的时候从当前位置往前减，减到0为止，不过这样会很慢，我用个链表维护，如果是0就直接跳过去了。
【实测不用链表真心TLE。。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<set> 7 using namespace std; 8 #define Maxn 250010 9 #define LL long long 10 11 int a[Maxn],b[Maxn],c[Maxn]; 12 LL d[Maxn]; 13 int lt[Maxn],nt[Maxn]; 14 15 bool cmp(int x,int y) 16 { 17 if(b[x]==b[y]) return x>y; 18 return b[x]<b[y]; 19 } 20 21 int n; 22 23 void add(int x,int y) 24 { 25 for(int i=x;i<=n;i+=i&(-i)) 26 d[i]+=y; 27 } 28 29 LL query(int x) 30 { 31 LL ans=0; 32 for(int i=x;i>=1;i-=i&(-i)) 33 ans+=d[i]; 34 return ans; 35 } 36 37 int op[Maxn]; 38 39 int main() 40 { 41 scanf("%d",&n); 42 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 43 for(int i=1;i<=n;i++) scanf("%d",&b[i]); 44 for(int i=1;i<=n;i++) c[i]=i; 45 memset(d,0,sizeof(d)); 46 for(int i=1;i<=n;i++) add(i,a[i]); 47 for(int i=1;i<=n;i++) nt[i]=i+1; 48 for(int i=1;i<=n;i++) lt[i]=i-1; 49 for(int i=1;i<=n;i++) if(a[i]==0) 50 { 51 lt[nt[i]]=lt[i]; 52 nt[lt[i]]=nt[i]; 53 } 54 sort(c+1,c+1+n,cmp); 55 op[0]=0; 56 for(int i=1;i<=n;i++) 57 { 58 if(query(c[i])>=b[c[i]]) 59 { 60 op[++op[0]]=c[i]; 61 int nw=c[i]; 62 while(nw&&a[nw]<=b[c[i]]) 63 { 64 add(nw,-a[nw]); 65 b[c[i]]-=a[nw]; 66 a[nw]=0; 67 lt[nt[nw]]=lt[nw]; 68 nt[lt[nw]]=nt[nw]; 69 nw=lt[nw]; 70 nw--; 71 } 72 if(b[c[i]]) 73 { 74 a[nw]-=b[c[i]]; 75 add(nw,-b[c[i]]); 76 } 77 } 78 } 79 sort(op+1,op+1+op[0]); 80 printf("%d\n",op[0]); 81 for(int i=1;i<=op[0];i++) printf("%d ",op[i]); 82 printf("\n"); 83 return 0; 84 }
方法二：【来者不拒】
能选的先选，选了的bi用一个最大堆维护，如果不行就把最大的bi弄出来让现在的满足。
2017-01-21 10:47:36
【BZOJ 2802】 2802: [Poi2012]Warehouse Store （贪心）
原文：http://www.cnblogs.com/Konjakmoyu/p/6336597.html
