Educational Codeforces Round 96 (Rated for Div. 2) 解题报告

CF1430B Barrels

Educational Codeforces Round 96 第二题,签到题。

题目链接

题意翻译

  • 多组数据,数据组数为 \( t \);
  • 有 \( n \) 个容量无限大的水桶,每个水桶里装有 \( a _ i \) 单位体积的水,每次操作可以选择两个水桶倒水,把其中一个水桶里任意多的水倒入另一个水桶。
  • 求至多 \( k \) 次操作后,水桶内装水量极差的最大值。
  • 数据范围:\( 1 \leq t \leq 10 ^ 3 \),\( 1 \leq k < n \leq 2 \cdot 10 ^ 5 \),\( 0 \leq a _ i \leq 10 ^ 9 \),\( \sum n \leq 2 \cdot 10 ^ 5 \)。

题解

显然把最大的 \( k + 1 \) 个水桶里面的水合在一起的总体积就是答案(最小值为 \( 0 \))。考虑这题的数据范围比较松,就随便用了个快排。时间复杂度为 \( \Theta ( n \log _ 2 n ) \)。

#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void)
{
    reg char ch = getchar();
    reg int res = 0;
    while (ch < '0' || '9' < ch)
        ch = getchar();
    while ('0' <= ch && ch <= '9')
        res = 10 * res + ch - '0', ch = getchar();
    return res;
}

const int MAXN = 2e5 + 5;

int n, k;
int a[MAXN];

int main(void)
{
    reg int t = read(); //数据组数
    while (t--)
    {
        n = read(), k = read(); //读入 n,k
        for (reg int i = 1; i <= n; ++i)
            a[i] = read();                           //读入 a[]
        sort(a + 1, a + n + 1);                      //排序
        reverse(a + 1, a + n + 1);                   //倒转,使得 a[] 单调不上升
        reg ll ans = 0;                              //记得开 long long
        for (reg int i = 1; i <= min(k + 1, n); ++i) //求最大的 k+1 的水桶里面的水的总体积
            ans += a[i];
        printf("%lld\n", ans); //输出答案
    }
    return 0;
}
Pages: 1 2 3 4 5 6 7 8 9