有 n n n个陷阱，编号从 1 1 1到 n n n。你将按照顺序通过它们。第 i i i个陷阱对你提供 a i a_i ai点基本伤害。
有时候你可以跳过一个陷阱而不是通过这个陷阱。你可以跳过不超过 k k k个陷阱。跳过的陷阱不会对你造成任何伤害，但是跳过的陷阱右边的陷阱的伤害都会自动加 1 1 1（附加伤害）。
如果你跳过一个陷阱，你不会得到任何伤害（包括基本伤害和附加伤害）。而且附加伤害是会递增的。举个例子，如果你跳过一个基本伤害为 a i a_i ai的陷阱 i i i，而且你以前跳过了 3 3 3个陷阱，你将受到 ( a i + 3 ) (a_i+3) (ai+3)点伤害。
你要求出在跳过不超过 k k k个陷阱的前提下你将得到的最少伤害。
输入格式有多组测试数据。第一行为一个整数 t ( 1 ≤ t ≤ 100 ) t (1 le t le 100) t(1≤t≤100)表示测试数据组数。测试数据的描述如下。
第一行为两个整数 n n n和 k k k ( 1 ≤ n ≤ 2 ⋅ 1 0 5 , 1 ≤ k ≤ n ) (1 le n le 2 cdot 10^5,1 le k le n) (1≤n≤2⋅105,1≤k≤n)，表示陷阱的数目和可以跳过的陷阱数目。
第二行为 n n n个整数 a 1 , a 2 , … , a n ( 1 ≤ a i ≤ 1 0 9 ) a_1,a_2,dots,a_n (1 le a_i le 10^9) a1,a2,…,an(1≤ai≤109)表示每个陷阱的基本伤害。
所有测试数据的 n n n之和不会超过 2 ⋅ 1 0 5 2 cdot 10^5 2⋅105。
输出格式对所有测试数据，输出一个整数表示在跳过不超过 k k k个陷阱的前提下你将得到的最少伤害。
输入输出样例| 输入 | 输出 |
|---|---|
| 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 | 0 21 9 6 0 |
第一个测试数据，可以跳过所有陷阱，造成 0 0 0点伤害。
第二个测试数据，有 5 5 5种方法跳过陷阱：
1.不跳过任何陷阱。
总伤害： 5 + 10 + 11 + 5 = 31 5+10+11+5=31 5+10+11+5=31。
2.只跳过第一个陷阱。
总伤害： 0 + ( 10 + 1 ) + ( 11 + 1 ) + ( 5 + 1 ) = 29 0+(10+1)+(11+1)+(5+1)=29 0+(10+1)+(11+1)+(5+1)=29。
3.只跳过第二个陷阱。
总伤害： 5 + 0 + ( 11 + 1 ) + ( 5 + 1 ) = 23 5+0+(11+1)+(5+1)=23 5+0+(11+1)+(5+1)=23。
4.只跳过第三个陷阱。
总伤害： 5 + 10 + 0 + ( 5 + 1 ) = 21 5+10+0+(5+1)=21 5+10+0+(5+1)=21。
5.只跳过第四个陷阱。
总伤害： 5 + 10 + 11 + 0 = 26 5+10+11+0=26 5+10+11+0=26。
为得到最小的伤害，需要跳过第三个陷阱，所以答案是 21 21 21。
第三个测试数据，跳过陷阱的最优解是 1 , 3 , 4 , 5 , 7 1,3,4,5,7 1,3,4,5,7。
总伤害： 0 + ( 2 + 1 ) + 0 + 0 + 0 + ( 2 + 4 ) + 0 = 9 0+(2+1)+0+0+0+(2+4)+0=9 0+(2+1)+0+0+0+(2+4)+0=9。
题解易知，跳过陷阱的顺序和解无关。
因此，结论就非常简单了。
跳过收益最大的几个点。
每个点的收益，可以按照以下的规则计算。
假定有三个点 a a a， b b b， c c c，所处位置为 1 1 1， 2 2 2， 3 3 3
正序跳过的解是这样的：跳过1的收益是 a − 2 a-2 a−2，数组变成 b + 1 b+1 b+1， c + 1 c+1 c+1
再跳过 b + 1 b+1 b+1的收益是 b b b，数组变成 c + 2 c+2 c+2
再跳过 c + 2 c+2 c+2，可过。
反向跳过其实也一样。
a − 2 + b − 1 + c + 3 = a + b + c a-2+b-1+c+3=a+b+c a−2+b−1+c+3=a+b+c
3 = ( 1 + 2 ) × 2 ÷ 2 3=(1+2) times 2 div 2 3=(1+2)×2÷2
类似地， k ( k − 1 ) 2 frac{k(k-1)}{2} 2k(k−1)为单纯加上收益后的补充。
代码如下：
#includeusing namespace std; long long a[200001],s[200001]; int main() { int t; scanf("%d",&t); while(t--) { long long n,k,ans=0; scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++) scanf("%lld",&a[i]),s[i]=a[i]-n+i,ans+=a[i]; ans-=k*(k-1)/2; sort(s+1,s+n+1); for(int i=n;i>=n-k+1;i--) ans-=s[i]; printf("%lldn",ans); } return 0; }
