https://codeforces.com/problemset/problem/1684/D
给定n个陷阱，编号从1到n。你将按顺序一个接一个地通过它们。第i个陷阱对你造成ai点基础伤害。
与其穿过一个陷阱，你可以跳过它。你最多可以跳过k个陷阱。如果你跳过一个陷阱，它不会对你造成任何伤害。但是有一个额外的规则：如果你跳过一个陷阱，后面所有陷阱的伤害都增加1点（这是一个奖励伤害）。
请注意，如果你跳过一个陷阱，你不会受到任何伤害（既不是基础伤害也不是奖励伤害）。此外，奖励伤害是累积的，例如，如果你经过了一个基础伤害为ai的陷阱i，并且你已经跳过了3个陷阱，那么你会受到(ai+3)点伤害。
你需要找到如果允许跳过不超过k个陷阱时可能获得的最小伤害。
输入 输入包含多个测试用例。第一行包含一个整数t（1≤t≤100）——测试用例的数量。以下是每个测试用例的描述。
每个测试用例的第一行包含两个整数n和k（1≤n≤2⋅10^5，1≤k≤n）——陷阱的数量和允许你进行的跳过次数。
每个测试用例的第二行包含n个整数a_1，a_2，…，a_n（1≤a_i≤10^9）——所有陷阱的基础伤害值。
保证所有测试用例中n的总和不超过2⋅10^5。
输出 对于每个测试用例，输出一个整数——如果允许您跳过不超过k个陷阱，则可能获得的最小总伤害。
示例
Example
Input
Copy
5 4 4 8 7 1 4 4 1 5 10 11 5 7 5 8 2 5 15 11 2 8 6 3 1 2 3 4 5 6 1 1 7
Output
Copy
0 21 9 6 0
注意 在第一个测试用例中，允许你跳过所有陷阱并且不受任何伤害。
在第二个测试用例中，有5种方式可以跳过一些陷阱：
不跳过任何陷阱。总伤害：5+10+11+5=31。
跳过第1个陷阱。
总伤害：0-+(10+1)+(11+1)+(5+1)=29。
跳过第2个陷阱。
总伤害：5+0-+(11+1)+(5+1)=23。
跳过第3个陷阱。
总伤害：5+10+0-+(5+1)=21。
跳过第4个陷阱。
总伤害：5+10+11+0-=26。
为了获得最小的伤害，需要跳过第3个陷阱，因此答案是21。
在第三个测试用例中，最优的方案是跳过陷阱1、3、4、5和7：
总伤害：0+(2+1)+0+0+0+(2+4)+0=9。
题解:
首先我们应该明白一定会跳过k个陷阱,因为每次都选最后一个的话,就不会有伤害加1的情况了
假设第一个陷阱
如果跳过第i个陷阱,后面n - i个陷阱伤害会增加,但是后面还会跳过k - 1个陷阱 ai - (n - i) + k - 1
同理第二个k个,ai - (n - i) + k - 2 (i并不同)
第三个也一样,
变形一些我们可以发现
我们最终对答案的贡献是k个ai + i - n*k + k(k - 1)/2
由于要求最小伤害,伤害总和减去答案贡献即可
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;#define int long long
typedef pair<int,int> PII;
typedef unsigned long long ULL;
const int N = 5e5 + 10;
int mod = 998244353;
int a[N];
void solve()
{int n,k;cin >> n >> k;int ans = 0;for(int i = 1;i <= n;i++){cin >> a[i];ans += a[i];a[i] += i;}sort(a + 1,a + 1 + n);for(int i = n;i > n - k;i--){ans -= a[i];}cout << ans + n*k - k*(k - 1)/2 <<"\n";
}
signed main()
{ios::sync_with_stdio(0 );cin.tie(0);cout.tie(0);int t = 1;cin >> t;while(t--){solve(); }
}
