【题解】LOJ 2306 「NOI2017」蔬菜

Problem

有 $n$ 种蔬菜,每种蔬菜共有 $c_i$ 个,每天会变质 $x_i$ 个,每销售一单位蔬菜可获得 $a_i$ 的收益,销售某种蔬菜的第一个可获得 $s_i$ 的额外收益

注意:每一单位蔬菜的变质时间是固定的,不随销售发生变化

求前 $p_i$ 天能获得的最大收益

Thought

先考虑限制条件:每天变质 $x_i$ 单位的蔬菜

第一天能够选择该品种的蔬菜 $f_1\in[0,c_i]$
第二天能够选择该品种的蔬菜 $f_2\in[0,c_i-max(f_1,x_i)]$

那么可以通过限制后缀和来保证每天选择蔬菜数量合法,即 $g_i=\sum_{i}^{\infty}f_i$
其中 $\forall g_i,g_i\leq c-(i-1)x$

那么从后往前考虑的话,就是每天可以选择的蔬菜数量不断增加

假设没有额外收益的限制,至于要一个二叉堆来维护从后往前每天能够取的蔬菜价格的最大值,每天取前 $m$ 个最大的,然后判断该种蔬菜是否取光,若取光,在堆中删除该种蔬菜(必然是堆顶)

然后每天加入 $x_i$ 个蔬菜,判断是否从无到有,若没有,则在堆中加入该种蔬菜

由于存在性每种元素最多改变 $1$ 次,每天最多改变 $m$ 次,所以总次数是 $n+pm$ ,大概在 $1e6$ 的级别

那么考虑额外收益的情况,由于额外收益非常特殊,它需要在第一次选择时计算,那么考虑将它的权值放到最后时刻额外拿出来一个

但是当 $p$ 改变时,最后时刻也会改变,这会导致答案的变化

考虑算出 $p_{max}$ 的答案后如何转移到 $p_{max}-1$
由于我们每天卖出的蔬菜的数量从第 $1$ 天到第 $p_{max}$ 天肯定是类似于 $m,m,\cdots,d,0,0,\cdots$
假设第 $p_{max}$ 天卖了 $v$ 个蔬菜,那么只需要从当前卖出的蔬菜中选出 $v$ 个最小的丢掉即可

说的简单但是写起来需要注意细节,比如说一天要丢掉多少啥的 qwq

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
typedef long long ll;
const int N = 100010;
int n, m, k;
int a[N << 1] , c[N], x[N];
int p[N], P;
struct cmp1 {
    bool operator () (const int x, const int y) const {return a[x] < a[y];}
};
struct cmp2 {
    bool operator () (const int x, const int y) const {return a[x] > a[y];}
};
priority_queue < int, vector<int>, cmp2 > q1;//less
priority_queue < int, vector<int>, cmp1 > q2;//greater
vector <int> appear[N];
int use[N << 1];
int sta[20], top;
ll Ans[N];
int cal(int tim, int i) {
    if(i > n) return 1;
    return max(0, c[i] - (tim - 1) * x[i]);
}
int main() {
    n = read(); m = read(); k = read();
    for(int i = 1; i <= n; ++ i) {
        a[i] = read(); a[n + i] = a[i] + read();
        c[i] = read() - 1; x[i] = read();
    }
    for(int i = 1; i <= k; ++ i) {
        p[i] = read();
        P = max(P, p[i]);
    }
    for(int i = 1; i <= n; ++ i) {
        if(c[i] == 0) continue;
        if(x[i] == 0)
            appear[P].push_back(i);
        else {
            int t = min(P, (c[i] / x[i] + (c[i] % x[i] != 0)));
            appear[t].push_back(i);
        }
    }
    for(int i = 1; i <= n; ++ i) {
        if(x[i] == 0)
            appear[P].push_back(i + n);
        else {
            int t = min(P, ((c[i] + 1) / x[i] + ((c[i] + 1) % x[i] != 0)));
            appear[t].push_back(i + n);
        }
    }
    ll ans = 0;
    for(int i = P; i; -- i) {
        for(auto it : appear[i])
            q2.push(it);    
        while(top) {
            if(sta[top] != sta[top - 1])
                if(cal(i + 1, sta[top]) == use[sta[top]] && cal(i, sta[top]) > use[sta[top]])
                    q2.push(sta[top]);
            sta[top --] = 0;
        }
        while(top < m && !q2.empty()) {
            int get = q2.top();
            ++ use[get];
            if(use[get] == cal(i, get))
                q2.pop();
            sta[++ top] = get;
            ans += a[get];
            q1.push(get);
        }
    }
    int sum = q1.size();
    for(int i = P; i; -- i) {
        int del = max(0, sum - m * i);
        sum -= del;
        while(del) {
            ans -= a[q1.top()];
            q1.pop();
            -- del;
        }
        Ans[i] = ans;
    }
    for(int i = 1; i <= k; ++ i)
        printf("%lcppld\n", Ans[p[i]]);
    return 0;
}
Comments

添加新评论