题解：CF1725L Lemper Cooking Competition

题意

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

选定一个满足 $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

递增且没有负数。
于是本题就转化为了求逆序对数。无解的两种情况：

$s$ 中存在负数。
$s_n$ 不是最大值。因为 $s_n$ 不能参与交换。

CODE：

CPP

//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)

题解：CF1725L Lemper Cooking Competition

文章操作

题意

解法

相关推荐

评论

题解：CF1725L Lemper Cooking Competition