思路

贪心，最优解一定会用完 $k$ 个间隔。反证：假设最优解没有用完 $k$ 个间隔，由于 $k \le n$，必能找到一个落脚点 $a_i$，此时从上一次落脚点（可能为 $a_0$）直接跳到下一个落脚点（可能为 $a_n$），至少可减少 $a_i$ 伤害，这与它是最优解矛盾。

假设跳过 $a_{i}$ 会立即获得 $n - i$ 额外伤害，则从第一个被跳过的间隔获得的额外伤害会比实际多 $k - 1$（因为后续 $n - i$ 个位置，每个位置都会多一个额外伤害，总共多 $n - i$ 个，但后续一定会再跳过 $k - 1$ 个位置），第二个多 $k - 2$，依此类推，总共多 $\frac{k(k -1)}{2}$。因此无论选择哪些间隔跳过，多出的额外伤害都是一定的。

预处理出数组 $b$，满足 $b_i = a_i - (n - i)$，表示跳过 $a_i$ 可以规避多少伤害。要想获得最少伤害，等价于规避最多伤害，贪心，选择可以规避的最大的 $k$ 个（反证）。

时间复杂度 $O(n)$。

#include <iostream>
#include <vector>
#include <algorithm>

#define endl "\n"

using namespace std;
using LL = long long;

void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> b(n);

  LL sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> b[i];
    sum += b[i];
    b[i] -= n - (i + 1);
  }
  sort(b.begin(), b.end());
  reverse(b.begin(), b.end());
  for (int i = 0; i < k; i++) sum -= b[i];
  sum -= k * (k - 1LL) >> 1;
  cout << sum << endl;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}