题目描述

给定一个长度为 n 的非负整数序列 a1,a2,…,an。

你可以对该序列进行最多 k 次操作。

每次操作选择两个非 0 的元素 ai 和 aj，然后选择一个整数 c（0≤c≤ai），使得 ai 减少 ，aj 增加 c。

请问，在操作全部完成后，序列中的最大值和最小值之差是多少。

例如，如果初始序列为 [5,5,5,5] 而 k=1，则一种最优方案是将 a2 减少 5，将 a4 增加 5，得到序列 [5,0,5,10]，这样最大值和最小值之差为 10。

再例如，如果序列中的所有元素都为 0，则无法进行任何操作，所以最大值和最小值之差也为 0。

样例

2
4 1
5 5 5 5
3 2
0 0 0

算法1

就是数组中最大的k+1个数的和。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int a[200000+5];
int main(){
    int T ;
    long long TNT = 0;
    scanf("%d", &T);
    for(int i=1 ; i<=T ; i++){
        int n , k;
        scanf("%d%d", &n , &k);
        for(int j=1 ; j<=n ; j++)scanf("%d", &a[j]);
        sort(&a[1] , &a[n+1]);
        for(int j=0 ; j<=k ; j++){
            TNT = TNT + a[n-j];
        }
        printf("%lld\n", TNT);
        TNT = 0;
    }
    return 0;
}