CF2140C

题解

首先，如果 Alice 操作后，Bob 操作了，那么 Alice 可以把他的操作反走一遍，这时

f(a)

的值便会比第一次 Alice 操作后还大，所以对 Bob 来说，他最好在第一次就结束游戏。

所以决定权在 Alice 手中。

Alice 第一次操作肯定要找对答案贡献最大的

l,r

操作。这时候就有两种方案。

设没做任何操作时

f(a)

为

S

。

将奇数位和偶数位互换，此时对于要换的两个位

x

和

y

（

x

为奇数位，

y

为偶数位），此时

f(a)

为

S+|x-y|+2 \times a_{y}-2 \times a_{x}

，所以我们要求上式的最大值。

可以枚举每一个奇数位。此时若

y<x

，就要求

x-y+2 \times a_{y} - 2 \times a_{x}

最大值，把有关

x

的剥离出来，可以用前缀和数组维护

2 \times a_{i} -i

的最大值（

i

为偶数），然后就可以

O(1)

求；若

y>x

，同理，可以维护后缀

2 \times a_{i} +i

的最大值。

将奇偶性相同的位互换，此时对答案的贡献为两个位置相减，贪心去想，可得答案为最后一个奇数位减

1

。

时间复杂度

O(n)

。

代码

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int _;
ll n,a[N],s1[N],s2[N],ans,sum;
void solve() {
	scanf("%lld",&n),sum=0,s2[n+1]=0,ans=(n&1)?(n-1):(n-2);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sum+=(2*(i%2)-1)*a[i];
	for(int i=1;i<=n;i++) {
		if(i&1) s1[i]=s1[i-1];
		else s1[i]=max(s1[i-1],2*a[i]-i);
	}
	for(int i=n;i;i--) {
		if(i&1) s2[i]=s2[i+1];
		else s2[i]=max(s2[i+1],2*a[i]+i);
	}
	for(int i=1;i<=n;i+=2) ans=max(ans,max(s1[i]+i,s2[i]-i)-2*a[i]);
	printf("%lld\n",ans+sum);
	return;
}
int main() {
	scanf("%d",&_);
	while(_--) solve();
	return 0;
}

文章操作

题解

代码

相关推荐

评论

CF2140C