有一种显然错误的做法：每次从堆里取最大的，更新链表
比如 19,20,19 这样的话会先选20。但是很显然，选两个19带来的贡献可能是更好的
这时我们就要想一种能做到“反悔”的方法
其实只需要做一点点修改，每次再push一个“19+19-20”进去，一样是对的
那这个“19+19-20”的放在哪儿呢（编号）？只需要放在20的位置就行了，这样是正确的
其实这样做的本质 是重写了这个问题 将其变成“N-2个物品中选M-1”个的形式，如此一直化归，直到最后变成“N-2(M-1)个物品中选1个”
#include<bits/stdc++.h> #define N 200005 using namespace std; template<class T> inline void read(T &x) { x=0; int f=1; static char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if(ch=='-') f=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); x*=f; } priority_queue<pair<int,int> >q; int n,m,a[N],l[N],r[N],ans; bool vis[N]; int main() { read(n),read(m); if(m>(n/2)){ puts("Error!"); return 0; } for(int i=1;i<=n;i++) { read(a[i]); q.push(make_pair(a[i],i)); l[i]=i-1,r[i]=i+1; } l[1]=n,r[n]=1; while(m--) { while(vis[q.top().second]) q.pop(); int val=q.top().first; int now=q.top().second; q.pop(); ans+=val, a[now]=a[l[now]]+a[r[now]]-val; vis[l[now]]=vis[r[now]]=true; l[now]=l[l[now]],r[l[now]]=now; r[now]=r[r[now]],l[r[now]]=now; q.push(make_pair(a[now],now)); } cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9866190.html
相关资源：各显卡算力对照表！