CF1415E New Game Plus! 题解

题意：

你有 $n$ 个数 $c_{1 \cdots n}$ 和 $1$ 个初始为 $0$ 的计数器 boss bonus。

你可以任意选择一个尚未被选择过的 $c_{i}$ ，把 boss bonus 加上 $c_{i}$ 。

你也有 $k$ 次机会把 boss bonus 变成 $0$ 。

每次「选择数字前的 boss bonus 的和」记为你的收获。求收获的最大值。

注意 $c_{i}$ 和最后的收获可以为负数。

输入格式：

输入的第一行两个整数，分别是 $n,k$ 。

输入的第二行 $n$ 个整数，表示 $c_{1 \cdots n}$ 。

输出格式：

输出一行，最大收获。

数据范围：

$1 \leq n \leq 5 \times 10^5,0 \leq k \leq 5 \times 10^5,-1 \times 10^6 \leq c_{i} \leq 1 \times 10^6$

容易发现，这 $k$ 次机会，其实把 $c$ 就是分成了 $k+1$ 个集合。

每个集合的元素都有不上升的性质，否则一定存在一个集合使得这个元素放进去以后答案增大。

因此我们可以维护一个堆，记录这 $k+1$ 个集合，每次取出值最大的那个堆，往里面塞当前最大的 $c_i$ 。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 16))

int res,a[N];
priority_queue<int> q;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, k; cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n, greater<int>());
    for(int i = 1; i <= k + 1; i++) q.push(0);
    for(int i = 1; i <= n; i++)
    {
        int sum = q.top(); q.pop();
        res += sum; sum += a[i]; q.push(sum);
    }
    cout << res << '\n';
    return 0;
}