「USACO 2008」玩具

题目大意：「餐巾计划问题」加强版。$n \leq 5 \times 10^5$

凸函数证明待填坑。

贪心策略为，优先选取购买的玩具，其次从前往后选取慢洗店的玩具，如果都不行，再从后往前选取快洗店的玩具。

之所以快洗店的玩具从后往前选取，是因为前面的慢洗店玩具有可能会在下一天用到，所以要留着前面的，比如下面的样例：

4 1 3 3 1 4
3
1
1
4

最优方案是购买 $4$ 个玩具，第二天送 $1$ 个去快洗店（而非第一天），第一天送 $3$ 个去慢洗店，费用为 $25$。

#include <cstdio>
#include <cstring>
 
const int N = 5000005, INF = 0x7fffffff;
int q1[N], q2[N], q3[N], h1, h2, h3, t1, t2, t3;
int a[N], b[N], n, d1, d2, c1, c2, tc, ans = INF;
 
int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
int min(int x, int y) {
    return x < y ? x : y;
}
void swap(int &x, int &y) {
    x ^= y, y ^= x, x ^= y;
}
int calc(int k) {
    int res = k * tc;
    h1 = h2 = h3 = 1, t1 = t2 = t3 = 0;
    memcpy(b, a, sizeof a);
    for (int i = 1; i <= n; ++i) {
        while (h3 <= t3 && q3[h3] + d2 <= i)
            q2[++t2] = q3[h3], ++h3;
        for (int j = 1; j <= a[i]; ++j) {
            if (k) --k;
            else {
                while (h1 <= t1 && !b[q1[h1]]) ++h1;
                if (h1 <= t1 && q1[h1] + d1 <= i) --b[q1[h1]], res += c1;
                else {
                    while (h2 <= t2 && !b[q2[t2]]) --t2;
                    if (h2 <= t2) --b[q2[t2]], res += c2;
                    else return INF;
                }
            }
            q1[++t1] = i, q3[++t3] = i;
        }
    }
    ans = min(ans, res);
    return res;
}
 
int main() {
    int l = 1, r = 0;
    n = read(), d1 = read(), d2 = read(), c1 = read(), c2 = read(), tc = read();
    if (c1 > c2) swap(d1, d2), swap(c1, c2);
    for (int i = 1; i <= n; ++i) a[i] = read(), r += a[i];
    while (l < r) {
        int mid = l + (r - l >> 1);
        if (calc(mid) < calc(mid + 1)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", ans);
    return 0;
}

时间复杂度 $O(n \log n)$