传送门：题目
怎么说呢，水题一道，直接用小根堆解决
主要是想通过这道题学习C++STL里面heap的用法
最后还是没有纠结出来，然后发现手写也不会了，就在网上找了一段，挺简洁的，以后就用这个做模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstdio>

using namespace std;

const int MN = 100100;

int w[MN * 2] = {0};
int f[MN] = {0};
int n, m, s;

void push(int x) {
    int p;
    for (p = ++s; p > 1 && f[p >> 1] > x; f[p] = f[p >> 1], p >>= 1);
    f[p] = x;
}

int pop() {
    int p, c, tp;
    for (tp=f[p=1],c=2;c<s&&(f[c+=(c+1<s&&f[c + 1]<f[c])?1:0]<f[s]);f[p]=f[c],p=c,c<<=1);
    f[p] = f[s--];
    return tp;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        scanf("%d", &w[i]);
    }
    for (int i = 0; i < m; i++) push(0);
    for (int i = 0; i < n; i++) push(w[i] + pop());
    int mx = 0;
    for (int i = 0; i < m; i++) mx = max(mx, pop());
    cout << mx << endl;
    return 0;
}