CF1862E Kolya and Movie Theatre

这是一道关于电影观看和快乐值的题目。

题目给出了 n 场电影，每场电影能够带来一定的快乐值。但是如果距离上一次观看电影 cnt 天后再观看一场电影，这场电影带来的快乐值会减少 d*cnt（可能减少至负数）。现在要选择不超过 m 场电影观看，使得最终所获得的快乐值最大。

题目大意

有 $n$ 场电影，第 $i$ 场电影能够带来 $a_i$ 的快乐值，但是当距离上一次观看电影 $cnt$ 天后观看一场电影，这场电影带来的欢乐值会减少 $d·cnt$（可能减少至负数）。现在我们可以去选择观看 $n$ 场电影中的不大于 $m$ 场，使得最终所获得的欢乐值最大。

思路

一个非常重要的性质是，欢乐值的减少总量只与最后去看的那场电影的场次有关。画图或公式推导不难发现，若最后一次看电影是第 $i$ 天，则欢乐值的减少总量为 $d·i$。枚举最后一场电影的场次，滑动窗口维护前 $m$ 大的正整数及其总和，不断更新答案即可。

代码

ll n, m, d, a[maxN + 5], ans, sum;
void solve() {
    priority_queue<ll, vector<ll>, greater<ll>> q;
    ans = sum = 0;
    cin >> n >> m >> d;
    rep(i, 1, n) { cin >> a[i]; }
    rep(i, 1, n) {
        if (a[i] > 0) {
            q.push(a[i]);
            sum += a[i];
            if (q.size() > m) {
                sum -= q.top();
                q.pop();
            }
        }
        ans = max(ans, sum - i * d);
    }
    cout << ans << endl;
}