题目描述

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

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

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

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

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

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

算法

这题很容易可以想出一个贪心算法，即每次操作都选取最大的数和次大的数，就相当于是将最大的数加上次大的数，原问题就转化成了求数列中前k大的数。
现在来证明贪心的正确性：
题目要求最大值与最小值之差最小，而很明显最小值会大于等于0。当最小值大于0时，我们肯定可以在其中一次操作中减去更多的数，而使其他的数更大。因此，每次操作都把较小的数减为0是一个正确的贪心策略。
现在我们知道了每次操作会把较小数减为0，从而把较大的数加上较小数。显然每次选更大的数作为操作中较小的数也是一个正确的贪心策略，那么问题就变成了较大的数怎么选。我们要选更大的数作为较小数，而另一个数还要比它更大。因此，每次就应该选择最大的数和次大的数来进行操作。这样，同时也使数列中的最大值更大。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int a[200010];

int main(){
    int t;
    cin>>t;
    while(t--){
        long long k,n,ans;
        cin>>n>>k;
        for(int i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n,greater<int>());
        ans=a[0];
        for(int i=1;i<=min(k,n-1);i++)
            ans+=a[i];
        cout<<ans<<endl;
    }
    return 0;
}