题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2151
似乎是半年+前讲过的。（然而看到的时候却不会了）
考虑贪心，限制就是不能选两边的。如果选了最大的又要反悔，一定不可能是要只选旁边的一个，而是把两个都选了；
所以选了这个以后，把两边的打上标记表示不能选，往堆里加入一个值为 两边的值-自己的值 的元素表示反悔选择即可。
维护两边是谁，自己用了链表。也许这就是自己很慢的原因？
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e5+;
int n,m,a[N<<],tot,ans,pr[N<<],nt[N<<];
bool vis[N<<];
struct cmp{
bool operator() (int u,int v)
{
return a[u]<a[v];
}
};
priority_queue<int,vector<int>,cmp> q;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();
return fx?ret:-ret;
}
int main()
{
n=rdn(); m=rdn(); tot=n;
for(int i=;i<=n;i++)
{
a[i]=rdn();q.push(i);
pr[i]=i-;nt[i]=i+;
}
if(m>(n>>)){puts("Error!");return ;}
pr[]=n; nt[n]=;
for(int i=,x,y,k;i<=m;i++)
{
k=q.top(); q.pop();
while(vis[k])k=q.top(),q.pop();
ans+=a[k]; x=pr[k]; y=nt[k];
a[++tot]=a[x]+a[y]-a[k]; q.push(tot);
vis[x]=; vis[y]=;
nt[pr[x]]=tot; pr[tot]=pr[x];
pr[nt[y]]=tot; nt[tot]=nt[y];
}
printf("%d\n",ans);
return ;
}