挺有意思的贪心
神奇的贪心
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #define rint register int using std::priority_queue; template <class T>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]<a[y.num]; } }; priority_queue<node>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 ",ans); return 0; }