New Game Plus!

/contest/1415/problem/E

感觉比D题要更简单

题面翻译

【题目大意】

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

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

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

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

1 ≤ n ≤ 5 × 1 0 5 , 0 ≤ k ≤ 5 × 1 0 5 , − 1 × 1 0 6 ≤ c i ≤ 1 × 1 0 6 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 1≤n≤5×105,0≤k≤5×105,−1×106≤ci​≤1×106。

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

【输入输出】

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

输入的第 2 2 2 行 n n n 个整数，表示 c 1 ⋯ n c_{1 \cdots n} c1⋯n​。

输出 1 1 1 行，最大收获。

The translation provider is @HPXXZYY.

题目描述

Wabbit is playing a game with n bosses numbered from 1 to n . The bosses can be fought in any order. Each boss needs to be defeated exactly once. There is a parameter called boss bonus which is initially 0 .

When the i -th boss is defeated, the current boss bonus is added to Wabbit’s score, and then the value of the boss bonus increases by the point increment ci . Note that ci can be negative, which means that other bosses now give fewer points.

However, Wabbit has found a glitch in the game. At any point in time, he can reset the playthrough and start a New Game Plus playthrough. This will set the current boss bonus to0, while all defeated bosses remain defeated. The current score is also saved and does not reset to zero after this operation. This glitch can be used at most k times. He can reset after defeating any number of bosses (including before or after defeating all of them), and he also can reset the game several times in a row without defeating any boss.

Help Wabbit determine the maximum score he can obtain if he has to defeat all n bosses.

输入格式

The first line of input contains two spaced integers n and k ( 1 \leq n \leq 5 \cdot 10^5 $ , $ 0 \leq k \leq 5 \cdot 10^5 $ ), representing the number of bosses and the number of resets allowed.

The next line of input contains $ n $ spaced integers $ c_1,c_2,\ldots,c_n $ ( $ -10^6 \leq c_i \leq 10^6 ), the point increments of the $ n $ bosses.

输出格式

Output a single integer, the maximum score Wabbit can obtain by defeating all $ n $ bosses (this value may be negative).

样例 #1

样例输入 #1

3 01 1 1

样例输出 #1

3

样例 #2

样例输入 #2

5 1-1 -2 -3 -4 5

样例输出 #2

11

样例 #3

样例输入 #3

13 23 1 4 1 5 -9 -2 -6 -5 -3 -5 -8 -9

样例输出 #3

71

提示

In the first test case, no resets are allowed. An optimal sequence of fights would be

Fight the first boss (+0) . Boss bonus becomes equal to 1 .Fight the second boss (+1) . Boss bonus becomes equal to 2 .Fight the third boss (+2) . Boss bonus becomes equal to 3 .

Thus the answer for the first test case is 0+1+2=3 .

In the second test case, it can be shown that one possible optimal sequence of fights is

Fight the fifth boss (+0) . Boss bonus becomes equal to 5 .Fight the first boss (+5) . Boss bonus becomes equal to 4 .Fight the second boss (+4) . Boss bonus becomes equal to 2 .Fight the third boss (+2) . Boss bonus becomes equal to -1 .Reset. Boss bonus becomes equal to 0 .Fight the fourth boss (+0) . Boss bonus becomes equal to -4 .

Hence the answer for the second test case is 0+5+4+2+0=11 .

思路：

除了操作k，其实感觉跟合并果子一样，优先队列，去写，首先排个序，然后大的肯定是优先选的，因为后期创造的价值更多，对于操作的话，其实应该是把最小的k个小于0的数处理成0.，所以我们可以在优先队列当中先插入k个0，然后这个题就演变成了合并果子这个题。

AC代码：

#include<bits/stdc++.h>using namespace std;using i64=long long;const int N=1e6+10; i64 a[N];priority_queue<i64>q;const i64 mod=1e9+7;void solve(){i64 n,k;cin>>n>>k;for(i64 i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1,[](i64 a,i64 b){return a>b;});for(i64 i=1;i<=k+1;i++){q.push(0);}i64 sum=0;//int j=0;for(int i=1;i<=n;i++){i64 op=q.top();q.pop();sum+=op;q.push(op+a[i]);}cout<<sum<<"\n";}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}}