【BZOJ 2802】 2802: [Poi2012]Warehouse Store （贪心）

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

鸣谢Oimaster

【分析】

　　可爱的贪心题。

　　【并没有秒，并且表示想了很久，并且表示样例调了挺久】

　　【幸好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
",op[0]);
81     for(int i=1;i<=op[0];i++) printf("%d ",op[i]);
82     printf("
");
83     return 0;
84 }

View Code

　　方法二：【来者不拒】

　　能选的先选，选了的bi用一个最大堆维护，如果不行就把最大的bi弄出来让现在的满足。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 using namespace std;
 8 #define Maxn 250010
 9 #define LL long long
10 
11 struct node
12 {
13     int x,id;
14     friend bool operator < (node x,node y)
15     {
16         return x.x<y.x;
17     }
18 };
19 
20 priority_queue<node > q;
21 
22 int a[Maxn],b[Maxn];
23 bool mark[Maxn];
24 
25 int main()
26 {
27     int n;
28     scanf("%d",&n);
29     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
30     for(int i=1;i<=n;i++) scanf("%d",&b[i]);
31     LL now=0;
32     int cnt=0;
33     while(!q.empty()) q.pop();
34     memset(mark,0,sizeof(mark));
35     for(int i=1;i<=n;i++)
36     {
37         now+=a[i];
38         if(now>=b[i])
39         {
40             mark[i]=1;
41             cnt++;
42             q.push((node){b[i],i});
43             now-=b[i];
44         }
45         else if(!q.empty()&&q.top().x>b[i])
46         {
47             now+=q.top().x-b[i];
48             mark[q.top().id]=0;
49             mark[i]=1;
50             q.pop();
51             q.push((node){b[i],i});
52         }
53     }
54     printf("%d
",cnt);
55     for(int i=1;i<=n;i++) if(mark[i])
56         printf("%d ",i);printf("
");
57     return 0;
58 }

View Code

2017-01-21 10:47:36