4946: [Noi2017]蔬菜

分析：

　　贪心。

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

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

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

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

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

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

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

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              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\n",ans[q[i]]);91 return 0;92 }

转载于:https://www.cnblogs.com/mjtcn/p/9681095.html

你可能感兴趣的文章