这个题气其实是对照巧妙的。如果选了第3个，就不能选2，4。假设3是最大的，如果选2必选4，qq空间破解访问权限206 ，选2了却不选4那么不如选3.如果最优解是选2，4，但是贪心的时候选了3，怎么弥补呢？把a[3]=a[2]+a[4]-a[3]再放到优先行列队伍里。

#include <iostream> #include <cstdio> #include <queue> #include <algorithm> #include <cmath> #include <cstring> #define inf 2147483647 #define N 1000010 #define p(a) putchar(a) #define For(i,a,b) for(long long i=a;i<=b;++i) //by war //2020.2.26 using namespace std; long long n,m,k,ans; long long a[N],l[N],r[N]; bool vis[N]; struct node{ long long w; long long id; bool operator < (const node &x) const{ return w<x.w; } }; priority_queue<node>q; void in(long long &x){ long long y=1;char c=getchar();x=0; while(c<‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();} while(c<=‘9‘&&c>=‘0‘){ x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();} x*=y; } void o(long long x){ if(x<0){p(‘-‘);x=-x;} if(x>9)o(x/10); p(x%10+‘0‘); } void del(long long x){ vis[x]=1; l[r[x]]=l[x]; r[l[x]]=r[x]; l[x]=r[x]=0; } signed main(){ in(n);in(m); if(m*2>n){ puts("Error!"); return 0; } For(i,1,n){ in(a[i]); r[i]=((i+1)%n==0?n:(i+1)%n); l[i]=(i-1==0?n:i-1); q.push((node){a[i],i}); } For(i,1,m){ while(vis[q.top().id]) q.pop(); node t=q.top();q.pop(); ans+=t.w; a[t.id]=a[l[t.id]]+a[r[t.id]]-a[t.id]; del(l[t.id]);del(r[t.id]); q.push((node){a[t.id],t.id}); } o(ans); return 0; }