序列操作

问题描述

存在一个序列 a, 是否存在一个数 K, 使得一些数加上 K，一些数减去 K，一些数不变，使得整个序列中所有的数相等。
其中对于序列中的每个位置上的数字，至多只能执行一次加运算或减运算或是对该位置不进行任何操作。

Input

输⼊第一行是一个正整数 t 表示数据组数。
接下来对于每组数据，输入的第一个正整数 n 表示序列 a 的长度，随后一行有 n 个整数，标号序列 a 。

Output

输出共包含 t 行，每组数据输出一行。对于每组数据，如果存在这样的 K，输出"YES"，否则输出"NO"。（输出不包含引号）

Sample

Input: 
2
5
1 2 3 4 5
5
1 2 3 4 5

Output: 
NO
NO

数据范围

数据点(上限)	t	n	ai
1, 2	10	10	10
3, 4, 5	10	103	109
6, 7, 8, 9, 10	10	104	1015

Limitation

Time limit		1000 ms
Memory limit	65536 kb

解题思路

操作只有，一些数加上k，一些数减去k，一些数不变，对于每一个数列，k恒定为一个数k或者其相反数。

可以把原数组排序，前面的数(小的数)加上k，中间的数不变，后面的数(大的数)减去k，所以一个数列中最多存在3个数：x - k, x, x + k，因此可以记录数列中有多少种不同的数。

如果不同的数种类 > 3，则不存在k；
若种类 = 1 或 2，则一定存在k；
若种类 = 3，则可以记录不同数出现的位置，记下这3个不同数：若(小的数+大的数)=2×中间的数，则一定存在k，否则k不存在。

模拟的时候，没有注意数据范围，用的int，后面几组数据WA了，后来改成long long 就过了……所以一定要留意数据范围啊！

源代码

#include <iostream>
#include <algorithm>
using namespace std;

bool solve(long long* a, int n) {
	sort(a, a + n);
	int count = 0;
	int dif[10];
	for (int i = 1; i < n; i++) {
		if (a[i] != a[i - 1]) {
			dif[count] = i;
			count++;
		}
		if (count > 2) {
			return false;
			break;
		}
	}
	if (count == 2) {
		long long x = a[dif[0] - 1];
		long long y = a[dif[0]];
		long long z = a[dif[1]];
		if (x + z != 2 * y)
			return false;
		else
			return true;
	}
	if (count == 1 || count == 0)
		return true;
}

int main() {
	int t;
	cin >> t;
	for (int ii = 0; ii != t; ii++) {
		int n;
		cin >> n;
		long long* a = new long long[n + 10];
		for (int i = 0; i < n; i++)
			cin >> a[i];
		bool ans = solve(a, n);
		if (ans)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}