Barrels CodeForces - 1430B

Barrels CodeForces - 1430B

你有 n 个桶放在一排, 从左到右开始编号分别为 1~n. 最初, 第 i 桶装的水是 ai 升.
你可以把水从一个桶倒到另一个桶。 在这个过程中, 你可以两个选择两个桶 x 和y (第 x个桶不应该为空) ，
然后从桶x 向桶 y 倒水(可能是所有的水).你可以假设桶的容量是无限的，所以你可以在每个桶里倒入任何数量的水。
如果最多可以倒水 k 次.计算桶中最大和最小水量之间的最大可能差。

举例：如果你有四个桶，每个桶里装 5 升水，k=1，你可以从第二个桶里倒5升水到第四个桶里，
所以桶里的水量是 [5,0,5,10]，最大和最小的差值是10；
如果所有的桶都是空的，你就不能做任何操作，所以最大和最小的量之差仍然是0。

Input

第一行包含一个整数 t (1 < t < 1000) — 测试用例的数量。
每个测试用例的第一行包含两个整数 n 和 k(1≤k<n<2e5) — 桶数和可以浇注的数量。
第二行包含 n 整数 a1, a2, ...... an (0≤ai≤1e9), 其中ai 是第 i 个桶的初始水量。
保证 n 个以上测试用例的总和不超过 2e5。

Output

对于每个测试用例，如果最多可以倒水k 次，请打印桶中最大和最小水量之间的最大可能差值。

Sample Input

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

Sample Output

10
0

分析

直接对水量升序排序，从大到小取 k 个水桶倒一起，sum+=a[i]。
如果 k 为 0，则直接用 （最大水 - 最小水）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,INF=0x3f3f3f3f;
int a[N];
int main() {
    // freopen("data.in", "r", stdin);
    int t,n,k; cin>>t;
    while(t--) {
        cin>>n>>k;
        for(int i=1; i<=n; i++) cin>>a[i];
        sort(a+1, a+1+n);
        LL sum=0;
        for(int i=n; i>=n-k; i--) sum += a[i];
        if(k>0) cout<<sum<<endl;
        else cout<<a[n]-a[1]<<endl;
    }
    return 0;
}