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

大致意思是

一排水桶n个，里面装了不同体积的水（数组a1a2……an），对这些桶的水进行k次分配（一次：两个桶之间进行分配），求：通过k次分配产生的最大差值（max-min）。

代码与思路：

思路一：

每次分配找最大（水的体积）与第二大的桶，然后把第二大的桶中水倒入最大的桶中。即：最大桶+=第二桶（水体积最多、第二多的桶，下同）

所以用算法表示就是，循环1找最大，循环2找第二大。

然后，在写代码时也发现了输入input的问题。这个题中数组个数和数组大小都是未知的。所以这里需要使用动态二维数组。

二维表示为：x y x表示输入样例 y表示样例中的桶。

此外，为了简便存储，方便后面使用，规定a[x][0],a[x][1]分别存储桶数n和分配次数k。

于是，代码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;
}

嗯，在本地完美运行，一提交就直接time limit。

有个注意点平常本地调试常用的system("pause");提交时一定要删除，不然直接timelimit

唔，看来是算法还不够简便了。

思路二：简单优化

上面的代码中有两次循环，如果桶的数目太多，效率就会很低。于是尝试将两次循环合并为一次循环：

大致思路：在循环过程同时寻找最大与第二大，每次都与两个同时比较。

注意：如果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;
}

虽然效率最起码提高了一倍，但是最终还是timelimit。

思路三：先排序再处理

这个本应该最容易想到的办法，我却最后才想到。哎，只能怪能力不足了。。

如小标题，直接调用标准库std::sort排序，代码写起来不要太简单。降序排序后，把第2个一直到k个桶都加到第一个桶（第一个到第k个求和），得出答案。

当然中间还出了一些小问题，数据溢出了。于是把大多int换成了long

个人感觉里面的二维数组std::sort排序过程比较有参考价值。

代码：

#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;
}