Luogu P5653 基础最优化练习题

题目描述

https://www.luogu.com.cn/problem/P5653

简要题意：你现在有一个数 $x$，初始为 $0$，接下来 $n$ 分钟，每分钟可以将其加上 $[-k,k]$，同时需要保证每分钟结束时 $x\le a_i$，令 $b_i$ 为第 $i$ 分钟结束时的数，现在有一个长度为 $n$ 的序列 $w_i$，最大化 $\sum_{i=1}^nb_iw_i$

$n\le 10^6$

Solution

首先我们将 $w$ 转换为后缀，那么如果在第 $i$ 步加了 $k$，那么会对总收益造成 $k\times suf_i$ 的影响，这样就能将每一步的贡献独立出来，那么现在唯一的限制就是前缀，注意到每个物品的代价本质是一样的（我们将每个物品拆成 $2k$ 个即可），我们考虑反悔贪心，令 $c_i$ 为物品的价值

注意到因为代价只有上界限制，所以我们使用以 $c$ 排序的大根堆，堆里同时存储 $c$ 和可以撤回的量

对于 $c>0$ 的物品，我们直接花代价 $k$ 来获得最大价值，然后扔到堆里

对于 $c<0$ 的物品，我们直接花代价 $-k$ 来获得最大价值

然后如果超出限制，我们再通过反悔贪心来减少某些位置的选择

#include <iostream>
#include <cstdio>
#include <queue>
#define maxn 1000010
#define ll long long
using namespace std;

int n, k, a[maxn], b[maxn];

ll suf[maxn];

struct node {
    int k; ll v;

    friend bool operator < (const node &u, const node &v) { return u.v > v.v; } 
} ;
priority_queue<node> Q; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    for (int i = n; i; --i) suf[i] = suf[i + 1] + b[i];
    ll ans = 0; 
    for (int i = 1, s = 0; i <= n; ++i) {
        if (suf[i] > 0) s += k, ans += k * suf[i], Q.push({ 2 * k, suf[i] });
        else s -= k, ans -= k * suf[i];
        while (s > a[i]) {
            node t = Q.top(); Q.pop(); int p = min(s - a[i], t.k);
            ans -= p * t.v; s -= p; if (t.k > p) Q.push({ t.k - p, t.v }); 
        }
    } cout << ans << "\n"; 
    return 0;
}