【ACWing】3627. 最大差值

题目地址：

https://www.acwing.com/problem/content/3630/

给定一个长度为$n$的非负整数序列$a_1,a_2,\dots ,a_n$。你可以对该序列进行最多$k$次操作。每次操作选择两个非$0$的元素$a_i$和$a_j$，然后选择一个整数$c$（$0\le c\le a_i$），使得$a_i$减少$c$，$a_j$增加$c$。请问，在操作全部完成后，序列中的最大值和最小值之差是多少。例如，如果初始序列为$[5,5,5,5]$，而$k=1$，则一种最优方案是将$a_2$减少$5$，将$a_4$增加$5$，得到序列$[5,0,5,10]$，这样最大值和最小值之差为$10$。再例如，如果序列中的所有元素都为$0$，则无法进行任何操作，所以最大值和最小值之差也为$0$。

输入格式：
第一行包含整数$T$，表示共有$T$组测试数据。
每组数据第一行包含整数$n$和$k$。
第二行包含$n$个整数$a_1,a_2,\dots ,a_n$。

输出格式：
每组数据输出一行，一个整数，表示可以得到的最大差值。

数据范围：
对于前三个测试点，$1\le n\le 10$。
对于全部测试点，$1\le T\le 1000$，$1\le k<n\le 2\times 10^5$，$0\le a_i\le 10^9$，每个输入的$T$组数据的$n$之和不超过$2\times 10^5$。

要求最大差值，首先，经过$k$次操作，一定可以让最小值变为$0$，而最大值最多可以变为$a$的最大$k$个数之和，而这两者是可以同时取到的。代码如下：

#include 
#include 
using namespace std;

const int N = 2e5 + 10;
int n, k, a[N];

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {  
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n, greater<int>());
    long res = 0;
    for (int i = 1; i <= k + 1; i++) res += a[i];
    printf("%ld\n", res);
  }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

每组数据时间复杂度$O(n\log n)$，空间$O(1)$。