CF1779C Least Prefix Sum 题解

· · 题解

可能更好的阅读体验

题目传送门

题目大意

给定一个序列 a，长度 n。
每次操作可以把 a_i 变成 -a_i。
要求 a 做前缀和之后的序列 s 中最小值为 s_m。
求最小操作次数。

n\le 2\times10^5

题目解析

显然你需要保证：

考虑第一条，显然我们可以倒着来，如果遇到后缀和大于零的，显然是把之后那部分最大的数变成负的。
然后考虑第二条，如果此时前缀和小于等于零，就把前面最小的变成正的。
显然用个堆维护一下最值就好。第一次Div1A用堆，感觉好离谱。
时间复杂度 \Theta(n\log n)

int n,m,a[maxn];
priority_queue<int> bi,EB;
priority_queue<int,vector<int>,greater<int> > sm,ES;
void work(){
    n=read(); m=read(); int i,ans=0; ll sum; for(i=1;i<=n;i++) a[i]=read();
    bi=EB; sm=ES; sum=0;
    for(i=m;i>=2;i--){
        sum+=a[i]; bi.push(a[i]);
        while(sum>0) sum-=bi.top()*2,bi.pop(),ans++;
    } sum=0;
    for(i=m+1;i<=n;i++){
        sum+=a[i]; sm.push(a[i]);
        while(sum<0) sum-=sm.top()*2,sm.pop(),ans++;
    } print(ans),pc('\n'); return;
}