题意

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

题解

假设我们观看了第 $i_1, i_2 ... i_s$ 这 $s$ 场电影，那么我们获得的欢乐值表示为

$a_{i_1} - i_1 \cdot d + a_{i_2} - (i_2 - i_1) \cdot d + ... + a_{i_s} - (i_s - i_{s - 1}) \cdot d$

将 $d$ 提取出来得到：

$a_{i_1} + a_{i_2} + ... + a_{i_s} - i_s \cdot d$

由此可见，$d$ 的系数仅与看的最后一场 $i_s$ 有关，因此我们可以枚举看的最后一场电影，得到 $- i_s \cdot d$ 的取值，随后贪心选择第 $i_1 ... i_{s-1}$ 场电影。

Code

#include <iostream>
#include <queue>
typedef long long ll;
using namespace std;
const int maxn = 200010;
int t, n, m;
ll d, ans, a[maxn];
priority_queue <pair <ll, int>> q;
int main () {
  ios::sync_with_stdio (false), cin.tie (0);
  cin >> t;
  while (t--) {
    cin >> n >> m >> d;
    ans = 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    ll sum = 0;
    while (q.size ()) q.pop ();
    for (int i = 1; i <= n; i++) { //枚举 i_s
      ans = max (ans, sum + a[i] - d * i);
      if (a[i] > 0) { //选择a[i]最大的m场（当然如果是负数就显然不会选）
        q.push ({-a[i], i});
        sum += a[i];
        if (q.size () >= m) {
          sum += q.top ().first;
          q.pop ();
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}