记录编号	569585	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]种树	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.163 s
提交时间	2022-03-09 23:03:14	内存使用	1.23 MiB

#include <cstdio>
#include <queue>
#include <vector>

using PII = std::pair<int, int>;

const int N = 200010;

int n, k, res;
int a[N], l[N], r[N];
bool st[N];
std::priority_queue<PII> q;

int main() {
    freopen("nt2011_tree.in", "r", stdin);
    freopen("nt2011_tree.out", "w", stdout);
    scanf("%d%d", &n, &k);
    if(k > (n >> 1)) {
        puts("Error!");
        return 0;
    }
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) {
        l[i] = i - 1, r[i] = i + 1;
        q.push((PII){a[i], i});
    }
    l[1] = n, r[n] = 1;
    for (int i = 1; i <= k; ++i) {
        while (st[q.top().second]) q.pop();
        int x = q.top().first, pos = q.top().second; q.pop();
        res += x;
        st[l[pos]] = st[r[pos]] = true;
        a[pos] = a[l[pos]] + a[r[pos]] - x;
        l[pos] = l[l[pos]], r[pos] = r[r[pos]];
        r[l[pos]] = pos, l[r[pos]] = pos;
        q.push((PII){a[pos], pos});
    }
    printf("%d", res);
    return 0;
}