挺有意思的贪心

神奇的贪心

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define rint register intusing std::priority_queue;template 
          
           inline void read(T &X){ X=0;int W=0;char ch=0; while(!isdigit(ch))W|=ch=='-',ch=getchar(); while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); X=W?-X:X;return;}int n,m,pre[200010],nxt[200010],vis[200010]={ 0};long long ans=0,a[200010];struct node{ int num; friend bool operator <(node x,node y) { return a[x.num]
           
            q;int main(){ read(n),read(m); if(m>(n>>1)){printf("Error!");return 0;} node x; for(rint i=1;i<=n;++i) { read(a[i]); pre[i]=(i==1)?n:i-1,nxt[i]=(i==n)?1:i+1; x.num=i,q.push(x); } while(m--) { for(x=q.top(),q.pop();vis[x.num];x=q.top(),q.pop()); ans+=a[x.num]; a[x.num]=a[pre[x.num]]+a[nxt[x.num]]-a[x.num]; vis[pre[x.num]]=vis[nxt[x.num]]=1; pre[x.num]=pre[pre[x.num]]; nxt[x.num]=nxt[nxt[x.num]]; nxt[pre[x.num]]=pre[nxt[x.num]]=x.num; q.push(x); } printf("%lld\n",ans);return 0;}