思路：
1.输出Error的情况：m>n/2
2.首先将饥饿值放到大根堆中，先喂最饿的猪i，则把i的饥饿值加到sum中；但也又可能喂i-1和i+1，所以此时需要反悔：把i取出来的同时，将a[i-1]+a[i+1]-a[i]放入堆中。（即保留取i，也保留取i-1和i+1的可能性），此时将i-1,i,i+1合并为一个节点
#include <bits/stdc++.h> using namespace std; const int N = 4e5 + 10; int n, m, l[N], r[N], ans, a[N], tot; bool mark[N]; struct node { int id, v; // v为饥饿值 bool operator<(const node &a) const { // 使用大根堆，重载<号 return v < a.v; } } tmp; priority_queue<node> q; // 大根堆 int main() { cin >> n >> m; if (m > n / 2) { cout << "Error!"; return 0; } else { for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 2; i < n; i++) { // 处理链表 l[i] = i - 1, r[i] = i + 1; q.push({i, a[i]}); } // 处理环形(使用链表存储) l[1] = n, r[1] = 2; l[n] = n - 1, r[n] = 1; q.push({1, a[1]}); q.push({n, a[n]}); tot = n; for (int i = 1; i <= m; i++) { tmp = q.top(); // 取出堆头节点放入tmp中 q.pop(); if (mark[tmp.id]) { // 如果已经被标记，即若取i,则标记i-1和i+1表示不能被取 i--; continue; } ans += tmp.v; // 没被标记，则加到答案中 // 新增节点 a[++tot] = a[l[tmp.id]] + a[r[tmp.id]] - a[tmp.id]; q.push({tot, a[tot]}); // 合并成一个节点 // 更新链表中左右指针位置关系 // 因为取了i就不能取i-1和i+1，所以位置关系类似 // i-2 tot i+2 tot为i-1 i i+1 tmp为i l[tot] = l[l[tmp.id]]; // tot左边为i-2,即tmp的l的l r[l[l[tmp.id]]] = tot; // i-2的右边为tot r[tot] = r[r[tmp.id]]; // tot右边为i+2,即tmp的r的r l[r[r[tmp.id]]] = tot; // i+2的左边为tot // 将这三个节点标记为已被处理 mark[tmp.id] = mark[l[tmp.id]] = mark[r[tmp.id]] = 1; } cout << ans; return 0; } }
