题目链接

题解

以前看别人博客，在考场上用费用流做，一直以为这题是毒瘤网络流题

没想到竟然是贪心模拟题。。。

如果只有一个蔬菜呢？这就是一个经典的普及难度的贪心，正着推面临优先选择的困难，而逆着推由于不存在淘汰，所以可以贪心选最大的

首先\(s_i\)的限制很容易处理，只需将每一个蔬菜分出一个价值\(a_i + s_i\)且过期时间为该蔬菜最后一个的蔬菜

现在我们计算出每个蔬菜最晚放置的时间点，将每一天看做一个盒子，我们贪心地优先将价值大的蔬菜从它能放入的地方一直往前放

由于每个盒子最多放\(10\)个，我们用并查集合并相邻的放满的盒子，全部放置满只需\(O(10^5m)\)

但是这样对于每一个\(p\)都要算一次，实则不然，我们先算出最大的\(p\)的答案，发现前\(p - 1\)天能使用的蔬菜包含前\(p\)天能使用的蔬菜，我们用堆维护已放入的蔬菜，对于前\(p - 1\)天，我们只需把堆中的蔬菜减至\((p - 1)m\)即可

复杂度\(O(10^5mlogn)\)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define mp(a,b) make_pair
            
             (a,b)#define cls(s) memset(s,0,sizeof(s))#define cp pair
             
              #define LL long long intusing namespace std;const int maxn = 200005,maxm = 100005,INF = 1000000000;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}priority_queue
              
               
                ,greater
                
                  > q;LL cost[maxn],los[maxn],tot[maxn],E[maxn];LL p[maxn],Pi = 100000,used[maxn],ans;int n,m,K,N,pre[maxn],id[maxn];inline int find(int u){return u == pre[u] ? u : pre[u] = find(pre[u]);}inline bool cmp(const int& a,const int& b){ return cost[a] > cost[b];}void work(){ REP(i,N) id[i] = i; REP(i,Pi) pre[i] = i; used[0] = m; sort(id + 1,id + 1 + N,cmp); LL sum,Out; for (int i = 1; i <= N; i++){ int u = id[i],now; if (u > n){ now = find(E[u]); if (!now) continue; used[now]++; ans += cost[u]; q.push(cost[u]); if (used[now] == m) pre[now] = now - 1; } else { Out = 0; now = E[u]; for (; ; now--){ now = find(now); if (!now) break; sum = tot[u] - los[u] * (now - 1) - Out; if (!sum && !los[u]) break; else if (!sum) continue; if (sum >= m - used[now]){ Out += m - used[now]; ans += cost[u] * (m - used[now]); pre[now] = now - 1; REP(j,m - used[now]) q.push(cost[u]); used[now] = m; } else { Out += sum; used[now] += sum; ans += cost[u] * sum; REP(j,sum) q.push(cost[u]); } } } } p[Pi] = ans; for (int i = Pi - 1; i; i--){ while (q.size() > 1ll * m * i) ans -= q.top(),q.pop(); p[i] = ans; }}int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); N = n = read(); m = read(); K = read(); int s; for (int i = 1; i <= n; i++){ cost[i] = read(); s = read(); tot[i] = read(); los[i] = read(); cost[++N] = cost[i] + s; tot[N] = 1; tot[i]--; if (!los[i]) E[i] = E[N] = Pi; else if (tot[i] / los[i] >= Pi) E[i] = E[N] = Pi; else { E[i] = tot[i] / los[i] + (tot[i] % los[i] != 0); if (E[i] * los[i] > tot[i]) E[N] = E[i]; else E[N] = E[i] + 1; } } work(); while (K--) printf("%lld\n",p[read()]); return 0;}

转载于:https://www.cnblogs.com/Mychael/p/9236893.html

你可能感兴趣的文章