来一篇形象一点的题解。

考虑对于一个集合 $S$，他原来的价值为 $val$，长度为 $sz$，那么如果新加入一个元素 $x$ 那他的价值为 $\max(val, x + sz + 1)$。

然后考虑维护出这 $k$ 个集合。

每次对于一个 $a_i$，你考虑他去放到哪个集合里。

感觉上来说，我们肯定把他放到最优的那个集合里，但是最优的标准是什么？

增量法。对于每个集合维护 $t$ 表示这个集合至少需要 $t$ 就可以新增贡献。

拿堆维护一下，每次找最小的，然后贡献就是 $\max(0, a_i - t)$。所需的新的值为 $\max(t - 1, a_i - 1)$。

然后一开始把前 $k$ 个放进堆里就好。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 10, inf = 0x3f3f3f3f;

int n, k, a[N];

signed main()
{
    cin.tie(0)->ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    priority_queue<int, vector<int>, greater<int>> q;
    int ans = 0;
    for (int i = 1; i <= k; i++) {
        ans += a[i] + 1;
        q.push(a[i] - 1);
    }
    for (int i = k + 1; i <= n; i++) {
        auto p = q.top(); q.pop();
        ans += max(0ll, a[i] - p);
        q.push(max(p - 1, a[i] - 1));
    }
    cout << ans;
    return 0;
}