# Problem 1430B

CodeForces 1430B解题过程

## 题目

B. Barrels
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You have n barrels lined up in a row, numbered from left to right from one. Initially, the i-th barrel contains ai liters of water.

You can pour water from one barrel to another. In one act of pouring, you can choose two different barrels x and y (the x-th barrel shouldn’t be empty) and pour any possible amount of water from barrel x to barrel y (possibly, all water). You may assume that barrels have infinite capacity, so you can pour any amount of water in each of them.

Calculate the maximum possible difference between the maximum and the minimum amount of water in the barrels, if you can pour water at most k times.

Some examples:

if you have four barrels, each containing 5 liters of water, and k=1, you may pour 5 liters from the second barrel into the fourth, so the amounts of water in the barrels are [5,0,5,10], and the difference between the maximum and the minimum is 10;
if all barrels are empty, you can’t make any operation, so the difference between the maximum and the minimum amount is still 0.
Input
The first line contains one integer t (1≤t≤1000) — the number of test cases.

The first line of each test case contains two integers n and k (1≤k<n≤2⋅105) — the number of barrels and the number of pourings you can make.

The second line contains n integers a1,a2,…,an (0≤ai≤109), where ai is the initial amount of water the i-th barrel has.

It’s guaranteed that the total sum of n over test cases doesn’t exceed 2⋅105.

Output
For each test case, print the maximum possible difference between the maximum and the minimum amount of water in the barrels, if you can pour water at most k times.

Example
inputCopy
2
4 1
5 5 5 5
3 2
0 0 0
outputCopy
10
0

## 代码与思路：

### 思路一：

x表示输入样例
y表示样例中的桶。

#### 于是，代码1来了：

#include <iostream>
using namespace std;

int main()
{
int t;
cin >> t;
unsigned int **array;
array = new unsigned int *[t];
for (int i = 0; i < t; i++) //input
{
int n, k;
cin >> n >> k;
array[i] = new unsigned int[n + 2];
array[i][0] = n;
array[i][1] = k;
for (int j = 2; j < n + 2; j++)
{
cin >> array[i][j];
}
}
for (int i = 0; i < t; i++)
{

int imax;
for (int l = 0; l < array[i][1]; l++)
{
int max1 = 2, max2;
for (int m = 3; m < array[i][0] + 2; m++)
{
if (array[i][m] > array[i][max1])
max1 = m;
}
if (max1 == 2)
{
max2 = 3;
}
else
{
max2 = 2;
}

for (int m = 3; m < array[i][0] + 2; m++)
{
if (array[i][m] > array[i][max2] && m != max1)
max2 = m;
}

array[i][max1] += array[i][max2];
array[i][max2] = 0;
imax = array[i][max1];
}
cout << imax << endl;
}
return 0;
}


### 思路二：简单优化

• 注意：如果max1被替换新位置，那要把原来max1的值赋给max2，这样就能保证循环过程中max2一直是第二大的。

#### 直接上代码：

#include <iostream>
using namespace std;

int main()
{
int t;
cin >> t;
unsigned int **array;
array = new unsigned int *[t];
for (int i = 0; i < t; i++) //input
{
int n, k;
cin >> n >> k;
array[i] = new unsigned int[n + 2];
array[i][0] = n;
array[i][1] = k;
for (int j = 2; j < n + 2; j++)
{
cin >> array[i][j];
}
}
for (int i = 0; i < t; i++)
{
int imax;
for (int l = 0; l < array[i][1]; l++)
{
int max1 = 2, max2 = 3;
for (int m = 3; m < array[i][0] + 2; m++)
{
if (array[i][m] > array[i][max1])
{
max2 = max1;
max1 = m;
}
else if (array[i][m] > array[i][max2])
{
max2 = m;
}
}
array[i][max1] += array[i][max2];
array[i][max2] = 0;
imax = array[i][max1];
}
cout << imax << endl;
}
//system("pause");
return 0;
}

### 思路三：先排序再处理

#### 代码：

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

int main()
{
int t;
cin >> t;
unsigned long **array;
array = new unsigned long *[t];
for (int i = 0; i < t; i++) //input
{
int n, k;
cin >> n >> k;
array[i] = new unsigned long[n + 2];
array[i][0] = n;
array[i][1] = k;
for (int j = 2; j < n + 2; j++)
{
cin >> array[i][j];
}
}

for (int i = 0; i < t; i++)//start
{

sort(array[i]+2,array[i]+array[i][0]+2,greater<unsigned long>()); //sort
int m=3;
unsigned long long imax=array[i][2];
for(int j=0;j<array[i][1];j++,m++)
{
imax+=array[i][m];
}
cout<<imax<<endl;
}
//system("pause");
return 0;
}