题解：CF1725L Lemper Cooking Competition

Elairin176 · 2025-01-12 09:14:54 · 题解

Link

题意

定义一次操作为依次执行以下内容：

• 选定一个满足 2\le i<n 的整数 i。
• 令 a_{i-1}\gets a_{i-1}+a_i。
• 令 a_{i+1}\gets a_{i+1}+a_i。
• 令 a_i\gets-a_i。

现在进行若干次操作，求将 a 的每个元素都变为非负的操作次数。无解输出 -1。

解法

我们观察题面的三步操作，容易注意到执行完操作后整个数组的前缀和不变。
我们令 s 为 a 的前缀和数组，那么我们可以把操作转化为交换 s_i 和 s_{i-1}。让原数组非负就是让 s 递增且没有负数。
于是本题就转化为了求逆序对数。无解的两种情况：

CODE：

//luogu paste jo5j6ogx
cst int N=1e5;
int n,b[N+10],m;
ll s[N+10],a[N+10],ans;
umap<ll,int>mp;
il void add(int x,int y){
    while(x<=m){
        b[x]+=y;
        x+=lowbit(x);
    }
}
il int sum(int x){
    int s=0;
    while(x){
        s+=b[x];
        x-=lowbit(x);
    }
    ret s;
}
il int sum(int l,int r){ret sum(r)-sum(l-1);}
int main(void){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    n=read<int>();
    for(int i=1;i<=n;i++){
        a[i]=s[i]=s[i-1]+read<ll>();
        if(s[i]<0){
            write(-1);ret 0;
        }
    }
    for(int i=1;i<n;i++){
        if(s[i]>s[n]){
            write(-1);ret 0;
        }
    }
    sort(a+1,a+n);
    m=unique(a+1,a+n)-a-1;
    for(int i=1;i<=m;i++) mp[a[i]]=i;
    for(int i=1;i<n;i++){
        s[i]=mp[s[i]];
        ans+=sum(s[i]+1,m);
        add(s[i],1);
    }
    write(ans);
    ret 0;
}

Record(Codeforces)