初级守护
#include <iostream> #include <vector> #include <queue> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<ll> a(n + 2), l(n + 2), r(n + 2); vector<bool> vis(n + 2, false); priority_queue<pair<ll, int>> pq; // 初始化双向链表和收益数组 for (int i = 1; i <= n; ++i) { cin >> a[i]; l[i] = i - 1; r[i] = i + 1; pq.emplace(a[i], i); } // 设置边界 a[0] = a[n + 1] = -1e18; ll res = 0; while (k--) { // 跳过已标记的节点 while (vis[pq.top().second]) pq.pop(); auto [val, pos] = pq.top(); pq.pop(); if (val <= 0) break; // 收益非正时停止 res += val; // 合并相邻节点 a[pos] = a[l[pos]] + a[r[pos]] - a[pos]; vis[l[pos]] = vis[r[pos]] = true; // 更新链表指针 l[pos] = l[l[pos]]; r[pos] = r[r[pos]]; r[l[pos]] = pos; l[r[pos]] = pos; // 将新节点加入优先队列 pq.emplace(a[pos], pos); } cout << res << endl; return 0;}
