嘘~ 正在从服务器偷取页面 . . .

CF1415E New Game Plus! 题解

发布日期: 2024-01-20

更新日期: 2024-01-20

文章字数: 475

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)\)

代码：

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