【P3826】 [NOI2017] 蔬菜

肖然 · 2023-09-19 15:00:22 · 个人记录

题意：有 n 种蔬菜，第 i 种蔬菜数量 c[i]，售价 a[i]，第一次额外收益 s[i]，每天损耗 x[i]。

每天能卖 m 单位，问卖前 1,2,...,p 天的最大收益

数据范围 n,p\le 10^5, m\le 10

把第一次额外收益看成 1 单位售价 a[i]+s[i] 的菜，每天损耗 x[i] 看成一种菜分成很多份，每份的消失时间不同。

那么可以看成总共有 np+n 种菜，注意：

• 若菜没有损耗，则视为在第 p 天出现，否则在第 \lceil (c-1)/x \rceil 天出现；
• 若 (c-1)|x，初始x0=x，否则 x0=(c-1) \% x；
• 若菜的出现时间大于询问的时间，需要把增加的 x[i] 先加上；

对于单组询问 p，是一个经典贪心模型，有三种传统做法。

模板题见：https://www.luogu.com.cn/problem/P2949

【做法1】贪心反悔

把菜按消失时间从小->大排序，用一个小根堆维护当前卖出的所有菜。枚举到第 i 个菜，若堆的sz小于其过期时间，直接加入堆；否则看堆顶售价是否小于第 i 个菜，若是就拿这个菜替换掉堆顶。最终答案就是堆里的总和。

【做法2】时光倒流

把菜按消失时间从大->小排序，用一个大根堆维护当前能够卖出的所有菜。时光倒流，看成菜在某一时刻出现、之后一直存在。到达一个时刻时，先把这个时刻出现的所有菜加入堆中，然后弹出最大在这天卖出。最终答案就是每天卖出的总和。如果时间值域太大的话可以用双指针实现。每次取单价最大的蔬菜：

• 假如卖掉之后还有，加回去。
• 假如卖掉之后没了，不加回去。
• 每天蔬菜的新增是不用显式维护的，只需要把上一天卖空的蔬菜检查一遍是否需要重新加回优先队列即可，而卖空的蔬菜每天不超过 m 种。

【做法3】贪心覆盖

把菜按售价从大->小排序后，从消失时间开始从后往前找空位放。可以用并查集实现，如果时间值域太大的话可以用动态开点线段树实现。

在本题中，【做法2/3】都可以优化到 O(mp) 做一次，方法就是把所有菜加入售价的大根堆，维护每种菜剩的数量，根据数量可以 O(1) 算出当前这份菜的出现时间。那么对 p=10^5 做一次，同时求出解集（就是卖出的菜集合，大小为 O(mp)）。发现 p-1 天的解集肯定是 p 天解集的一个子集，并且肯定是其去掉最小的 m 份菜（最优性&可行性），利用这个结论就把 p=10^5 的解集sort一下之后就可以求出每天的解集了。

总复杂度 O(mplogmp + q)。

//100pts
#include<bits/stdc++.h>
#define MAXN 1000005
using namespace std;
typedef long long ll;

int my_ceil(int a, int b){
    return (a+b-1)/b;
}

int n,m,q;
int tmax = 1e5;
int fa[MAXN];
int findr(int x){
    if(fa[x]==x) return x;
    else return fa[x] = findr(fa[x]);
}

struct node{
    int a,c,x,st;
    node(int a=0, int c=0, int x=0, int st=0):a(a), c(c), x(x), st(st){}
    bool operator < (const node& n1) const{
        return a > n1.a;
    }

    int cal_t(){
        if(st) return findr(st);//a+s
        else if(x) return findr(min(my_ceil(c,x), tmax));//a
        else return findr(tmax);//x=0
    }
} v[MAXN];

ll ans[MAXN];
int res[MAXN], cnt = 0;
int r[MAXN];

void solve(){
    for(int i=1;i<=tmax;i++){
        r[i] = m;
        fa[i] = i;
    }

    int t;
    for(int i=1;i<=n;i++){
        while((t=v[i].cal_t()) && v[i].c){
            res[++cnt] = v[i].a;
            --r[t]; --v[i].c;
            if(r[t]==0) fa[t] = findr(t-1);
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>q;

    int a,s,c,x;
    for(int i=1;i<=n;i++){
        cin>>a>>s>>c>>x;
        if(x) v[i] = node(a+s, 1, x, min(tmax,my_ceil(c,x)));
        else v[i] = node(a+s, 1, x, tmax);
        v[n+i] = node(a, c-1, x, 0);
    }

    n = 2*n;
    sort(v+1, v+1+n);
    solve();

    ll tot = 0;
    for(int i=1;i<=m*tmax;i++){
        tot += res[i];
        ans[my_ceil(i,m)] = tot;
    }

    int qt;
    while(q--){
        cin>>qt;
        cout<<ans[qt]<<'\n';
    }
    return 0;
}