4946: [Noi2017]蔬菜

http://www.lydsy.com/JudgeOnline/upload/Noi2017D2.pdf

分析：

　　贪心。

　　首先可以将一个蔬菜拆成两个，一个是有加成的，一个是没有加成的。

　　贪心：1、多卖出些贵的好，所以先考虑贵的蔬菜；2、对于一个蔬菜，卖的越晚越好（越晚，可以给前面留出位置。）

　　然后对蔬菜按价格排序，从后往前考虑卖的时间，尽量卖。如果一天的m个蔬菜全卖了，那么下次走到这个位置就没用了，所以直接并查集合并即可。所以复杂度是$O(mn imes 并查集的复杂度)$。现在可以贪心的处理出任意天的最大买的获益。

　　如果对于每次询问都这样做，显然会超时。考虑优化。如果知道某一天，是否可以快速的知道相邻的一天。　

　　正着考虑，每次加入一些位置，因为上面的贪心是从最后一天贪心的，现在最后一天变了，所以无法推出下一天，没有什么关系。

　　正难则反，反过来考虑，每次相当于减去一些蔬菜，所以可以减去最便宜的。

　　做法：用上面的贪心处理处n天的最大获益，并记录每天卖了多少，用栈记录所有卖的蔬菜（上面的一定是价值小的），然后计算这一天需要减去多少颗蔬菜，从栈顶开始减。复杂度$O(n+D)$。

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<cctype>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<map>
11 #define fi(s) freopen(s,"r",stdin);
12 #define fo(s) freopen(s,"w",stdout);
13 using namespace std;
14 typedef long long LL;
15 
16 inline int read() {
17     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
18     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
19 }
20 
21 const int N = 200010;
22 
23 struct Node{
24     int w, siz, sub, d; // 价值，数量，每天减少的，消失的一天 
25     Node() {}
26     Node(int _w,int _siz,int _sub,int _d) { w = _w, siz = _siz, sub = _sub, d = _d; }
27     bool operator < (const Node &A) const {
28         return w > A.w;
29     }
30 }A[N];
31 int n, m, k, Top;
32 int sk[N], skw[N], d[N], fa[N], q[N];
33 LL ans[N], sumr[N], del[N], Sum;
34 
35 int find(int x) {
36     return x == fa[x] ? x : fa[x] = find(fa[x]);
37 }
38 void Merge(int a,int b) {
39     a = find(a), b = find(b);
40     if (a != b) fa[a] = b;
41 }
42 void Calc(int i,int s,int w) { // 第i天，卖价值为w的菜，卖了s个 
43     Sum += 1ll * s * w;
44     d[i] += s;
45     sk[Top] += s, skw[Top] = w; // skw[Top]+=w!!! 
46     if (d[i] == m) Merge(i, i - 1);
47 }
48 int main() {
49     n = read(), m = read(), k = read();
50     int tot = 0, D = 0;
51     for (int i=1; i<=n; ++i) {
52         int w = read(), fir = read(), siz = read(), sub = read();
53         A[++tot] = Node(w + fir, 1, 0, sub ? (siz - 1) / sub + 1 : N - 10);
54         if (--siz) A[++tot] = Node(w, siz, sub, sub ? (siz - 1) /sub + 1 : N - 10);
55     }
56     for (int i=1; i<=k; ++i) 
57         q[i] = read(), D = max(q[i], D);
58 
59     sort(A + 1, A + tot + 1);
60     for (int i=0; i<=D; ++i) fa[i] = i;
61     for (int i=1; i<=tot; ++i) {
62         ++Top;
63         int idx = find(min(A[i].d, D));
64         int sum = (idx - 1) * A[i].sub, r = A[i].siz - sum; // sum前面卖的，r现在卖的 
65         while (idx && r) {
66             int mn = min(m - d[idx], r); // d[idx] not d[idx - 1]
67             Calc(idx, mn, A[i].w);
68             r -= mn;
69             int p = idx;
70             idx = find(idx - 1);
71             p -= idx;
72             if (sum) r += p * A[i].sub, sum -= p * A[i].sub; //!!! 
73         }
74         if (!find(D)) break;
75     }
76     for (int i=1; i<=D; ++i) sumr[i] = sumr[i - 1] + m - d[i]; // 剩余的前缀和 
77     LL tmp = 0;
78     for (int i=D; i>=1; --i) del[i] = max(tmp - sumr[i], 0ll), tmp += d[i]; // 到第i天要删除的个数 
79     for (int i=D; i>=1; --i) {
80         ans[i] = Sum;
81         int now = del[i - 1] - del[i]; // 从第i天到第i-1天，要减去多少蔬菜。 
82         while (now) {
83             int mn = min(now, sk[Top]);
84             Sum -= 1ll * skw[Top] * mn; 
85             now -= mn;
86             sk[Top] -= mn;
87             if (!sk[Top]) Top --; 
88         } 
89     }
90     for (int i=1; i<=k; ++i) printf("%lld
",ans[q[i]]);
91     return 0;
92 }