题解：CF2117D Retaliation

这题运用了一个小技巧，就是先假设可以使数组爆炸，那么所有元素都一定相等。

这时只用考虑

a_1

和

a_2

两个元素，使它们两个相等，再看其它元素是否也相等并可以化为

0

。

分三种情况：

$a_1<a_2$ ，那么需要执行操作 $1$ 直至 $a_1$ 等于 $a_2$ ，因为这样 $a_1$ 所减的值才比 $a_2$ 小。
$a_1>a_2$ ，那么需要执行操作 $2$ 直至 $a_1$ 等于 $a_2$ ，因为这样 $a_1$ 所减的值才比 $a_2$ 大。
$a_1=a_2$ ，不用执行操作。

最后再所有元素是否相等并是否可以化成

0

就可以了。

其中，如果同时进行操作

1

和

2

，每个元素都加上

i+\left(n-i+1\right)

，两个

i

消掉，结果为

n+1

，所以只需要判断元素是否可以被

n+1

整除并且大于等于

0

就可以了。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N],n,T;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> T;
	while(T--){
		cin >> n;
		for(int i = 1;i <= n;++i){
			cin >> a[i];
		} 
		int x = abs(a[1] - a[2]);//操作要执行x次，因为每次操作a[1]和a[2]的差只会减少1
		if(a[1] < a[2]){
			for(int i = 1;i <= n;++i){
				a[i] -= x * i;//相当于削弱a[1]更少使其与a[2]相等 
			}
		}
		else{
			for(int i = 1;i <= n;++i){
				a[i] -= x * (n - i + 1);
			}
		}
		int flag = 1;//判断a数组的所有元素是否都相等
		for(int i = 2;i <= n;++i){
			if(a[i] != a[i - 1]){
				flag = 0;
				break;//有元素不相等 
			}
		} 
		if(flag == 1 && a[1] >= 0 && a[1] % (1 + n) == 0) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

题解：CF2117D Retaliation

文章操作

相关推荐

评论

题解：CF2117D Retaliation