本文共 2406 字，大约阅读时间需要 8 分钟。
//#include //#pragma comment(linker, "/STACK:1024000000,1024000000") #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; //#define ll long long #define ull unsigned long long#define pb push_back #define FOR(a) for(int i=1;i<=a;i++) #define sqr(a) (a)*(a)#define dis(a,b) sqrt(sqr(a.x-b.x)+sqr(a.y-b.y))ll qp(ll a,ll b,ll mod){ ll t=1;while(b){if(b&1)t=t*a%mod;b>>=1;a=a*a%mod;}return t;}struct DOT{ll x;ll y;};inline void read(int &x){int k=0;char f=1;char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())k=k*10+c-'0';x=k*f;} const int dx[4]={0,0,-1,1};const int dy[4]={1,-1,0,0};const int inf=0x3f3f3f3f; const ll Linf=0x3f3f3f3f3f3f3f3f;const ll mod=1e9+7;;const int maxn=2e5+3;int ans;struct heap{ int v,x,av;}h[maxn];int sz;int n,m,a[maxn];//readint cnt,v[maxn];//正块个数int tot; //选择数int pre[maxn],nxt[maxn],pos[maxn];void pushup(int x){ while(h[x].av >1].av){ pos[h[x>>1].x]=x; swap(h[x],h[x>>1]); x=x>>1; } pos[h[x].x]=x;}void push(int v,int x){ sz++;h[sz].v=v;h[sz].x=x;h[sz].av=abs(v); pos[x]=sz; pushup(sz);}void pushdown(int x){ int to; while((x<<1)<=sz){ to=(x<<1); if(to h[to+1].av)to++; if(h[x].av>h[to].av){ pos[h[to].x]=x; swap(h[to],h[x]); x=to; }else break; } pos[h[x].x]=x;}void del(int x){ h[x].av=inf; pushdown(x);}void solve(){ int a,b;heap k; for(int i=1;i<=cnt;i++)push(v[i],i); while(tot>m){ tot--; k=h[1]; if(pre[k.x]==-1){ if(k.v>0){ans-=k.v;del(1);} else{del(1);tot++;} pre[nxt[k.x]]=-1; }else if(nxt[k.x]==-1){ if(k.v>0){ans-=k.v;del(1);} else{del(1);tot++;} nxt[pre[k.x]]=-1; }else{ ans-=k.av; a=nxt[k.x];b=pre[k.x]; pre[k.x]=pre[b];nxt[pre[b]]=k.x; nxt[k.x]=nxt[a];pre[nxt[a]]=k.x; h[1].av=h[pos[a]].av+h[pos[b]].av-h[1].av; h[1].v+=h[pos[a]].v+h[pos[b]].v; pushdown(1); del(pos[a]);del(pos[b]); } } printf("%d\n",ans);}int main(){ scanf("%d%d",&n,&m); int tmp=0; for(int i=1;i<=n;i++){ int x;scanf("%d",&x); a[++tmp]=x; if(a[tmp]==0)tmp--; } v[++cnt]=a[1]; for(int i=2;i<=tmp;i++){ if(a[i]*a[i-1]>0)v[cnt]+=a[i]; else v[++cnt]=a[i]; } for(int i=1;i<=cnt;i++)if(v[i]>0){ans+=v[i];tot++;} for(int i=1;i<=cnt;i++){nxt[i]=i+1;pre[i]=i-1;} nxt[cnt]=-1;pre[1]=-1; solve();}
转载于:https://www.cnblogs.com/Drenight/p/8611194.html