题目链接

bzoj4946: [Noi2017]蔬菜

题解

挺神的贪心

把第次买的蔬菜拆出来，记下每种蔬菜到期的日期，填第一单位蔬菜比其他的要晚

按价格排序后，贪心的往前面可以填的位置填就可以了。找可以填的位置用并查集维护一下。这样就求出了最大天数的答案。

对于询问的答案，从最后一天往前推，把最便宜的那些丢掉就好了。

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#define gc getchar

#define pc putchar

#define int long long

inline int read() {

    int x = 0,f = 1;

    char c = getchar();

    while(c < '0' || c > '9') c = gc();

    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc();

    return x * f;

}

void print(int x) {

    if(x < 0) {

        pc('-'); x = -x;

    }

    if(x >= 10)print(x / 10);

    pc(x % 10 + '0');

}

const int maxn  = 200007;

int n,m,k;

struct node {

    int a,d,c,x;

    node(int a = 0,int c = 0,int x = 0,int d = 0) : a(a), c(c),x(x),d(d) {};

    bool operator < (const node &k) const {

        return a > k.a;

    }

} a[maxn];

int tot = 0;

int q[maxn],fa[maxn];

int find(int x ) {

    if(fa[x] != x) fa[x] = find(fa[x]);

    return fa[x];

}

void unionn(int x,int y) {

    int fx = find(x),fy = find(y);

    if(fx == fy) return ;

    fa[fy] = fx;

}

int cnt = 0;

int g[maxn],d[maxn],ga[maxn];

int sum = 0;

void calc(int idx,int c,int a) {

    sum += 1ll * c * a;

    g[cnt] += c;ga[cnt] = a;

    d[idx] += c;

    if(d[idx] == m) unionn(idx - 1,idx);

}

int L[maxn],upd[maxn];

int ans[maxn];

main() {

    //freopen("1.in","r",stdin);

    n = read(),m = read(),k = read();

    for(int aa,s,c,x,i = 1;i <= n;++ i) {

        aa = read(),s = read(),c = read(),x = read();

        a[++ tot] = node(aa + s,1,0,x ? (c - 1) / x + 1 : maxn - 7);

        if(-- c) a[++ tot] = node(aa,c,x,x ? (c - 1) / x + 1 : maxn - 7);

    }

    int maxd = 0;

    for(int i = 1;i <= k;++ i) maxd = std::max(maxd,q[i] = read());

    std::sort(a + 1,a + tot + 1);

    for(int i = 1;i <= maxd;++ i) fa[i] = i;

    for(int i = 1;i <= tot;++ i) {

        cnt ++;

        int idx = find(std::min(a[i].d,maxd)); //a 价值 d GG日期 d 数量 x 每天GG数

        int res = (idx - 1) * a[i].x ,now = a[i].c - res;

        while(idx && now) {

            int mn = std::min(m - d[idx],now);

            calc(idx,mn,a[i].a);

            now -= mn;

            int p = idx;

            idx = find(idx - 1);

            p -= idx;

            if(res) now += p * a[i].x , res -= p * a[i].x;

        }

        if(!find(maxd)) break ;

    }

    int R = 0;

    for(int i = 1;i <= maxd;++ i) L[i] = m - d[i] + L[i - 1];

    for(int i = maxd;i;-- i) upd[i] = std::max(R - L[i],0ll),R += d[i];

    for(int i = maxd;i >= 1;-- i) {

        ans[i] = sum;

        int tmp = upd[i - 1] - upd[i];

        while(tmp) {

            int mn = std::min(tmp,g[cnt]);

            sum -= 1ll * ga[cnt] * mn;

            tmp -= mn;

            g[cnt] -= mn;

            if(!g[cnt]) -- cnt;

        }

    }

    for(int i = 1;i <= k;++ i) print(ans[q[i]]),pc('\n');// print(10);

    return 0;

} // 1110001