C. Nezzar and Symmetric Array

題目大意

原來有2n個數，各不相同，這2n個數中，每個數的相反數也在其中，
Nezzar在100萬年前計算出了 每個數與其他數的差值 的和，但忘掉了原來那2n個數，
問從這2n個計算出來的差值和能不能推出一個滿足條件的2*n個數，

解題思路

首先原陣列中，一個數的差值和 與 這個數的相反數的差值和 是相同的，

舉個例子，假如原來這6個數是 ±2、±7、±9
那么

-2的差值和就是abs(2-(-2)) + abs(-7-(-2)) + abs(7-(-2)) + abs(-9-(-2)) + abs(9-(-2))

這就需要 條件一 差值和們 成對出現

因±差值和相同，故先只研究正值

先研究2：
2與-2的差值是兩個2（2的兩倍）
2與±7的差值和是兩個7（7的兩倍）
2與±9的差值和是兩個9（9的兩倍）

再研究7：
7與±2的差值和是兩個7（7的兩倍）
7與-7的差值是兩個7（7的兩倍）
7與±9的差值和是兩個9（9的兩倍）

最后研究9：
9與±2的差值和是兩個9（9的兩倍）
9與±7的差值和是兩個9（9的兩倍）
9與-9的差值是兩個9（9的兩倍）

所以有

這就需要 條件二 差值和都為偶數

并且由此，我們可以分別計算出每一個原來的數，

在計算程序中，每一個計算出的原來的數需要滿足一下條件：

條件三 原來的數是整數（可以整除）

條件四 原來的數各不相同

但是這樣交上去還是沒有考慮完所有的情況，還有一點就是計算出的原來的數的范圍：>1
這是因為前面我們是只考慮整數才得出的結論，所以如果計算程序中出現了負數（或0），就不可以繼續還原，

這就需要 條件五 計算程序中的數都是正數

總結

條件一：差值和們 成對出現
條件二：差值和都為偶數
條件三：原來的數是整數（可以整除）
條件四：原來的數各不相同
條件五：計算程序中的數都是正數

其中，條件三和條件五可以合并為

計算程序中的數都是正整數

總之，只需要滿足

條件一：差值和們 成對出現
條件二：差值和都為偶數
條件三：計算程序中的數都是正整數

AC代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll really[100010]; // Really 記錄真正需要處理的數（表格二左邊的1/2）
int main()
{
	int N;
	cin >> N;
	while (N--)
	{
		int n;
		scanf("%d", &n);
		bool buxing = 0; //不行的拼音
		map<ll, int> ma; //用map記錄出現了幾次（條件一）
		for (int i = 0; i < 2 * n; i++)
		{
			ll t;
			scanf("%lld", &t);
			if (t % 2) //差值和是否為偶數（條件二）
				buxing = 1;
			ma[t]++;
		}
		int sum = 1;
		ll realOriSum = 0;  // 已經得出的原來的數，上文樣例中便是 9  7  3
		if (buxing)
		{
			puts("NO");
		}
		else
		{
			for (map<ll, int>::iterator it = ma.begin(); it != ma.end(); it++)
			{
				if (it->second != 2) // 差值和是否都出現了兩處（條件一）
					buxing = 1;
				really[sum++] = (it->first) / 2;
			}
			if (buxing)
			{
				puts("NO");
			}
			else
			{
				for (sum--; sum > 0; sum--)
				{
					ll all = really[sum] - realOriSum;  //減去原來的數
					if (all % sum)  //是否可以整除
						buxing = 1;
					ll thisReal = all / sum;
					realOriSum += thisReal;
					if (thisReal <= 0)
						buxing = 1;
				}
				if (buxing)
				{
					puts("NO");
				}
				else
					puts("YES");
			}
		}
	}
	return 0;
}

2021-1-29更

如果沒看懂

上文中的例子原始陣列±2、±7、±9
那么題目要給的差值和為 36 36 46 54 46 54（順序不一定）
去重排序除以2（用really陣列保存）18 23 27
27/3=9，所以原始陣列中最大的數就是9
(23-9)/2=7，所以原始陣列中還有一個正數7
(18-9-7)/1=2，所以原始陣列中還有一個正數2

所以原始陣列為±2、±7、±9，輸出YES

注釋簡化版代碼

/*CSDN簡化版本*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;  // 用ll來代替long long
/*really[]
	題目給的是計算出的差值和，是無序且重復的
	這個really陣列就是用來有序地記錄這些差值和的一半的
	比如上文所舉的例子，±2、±7、±9
	那么題目所給的差值和就是 36 36 46 46 54 54
	而really陣列中要記錄的就是 18 23 27 （差值和的一半）
	除以二是因為表格二，差值和都是原數和的兩倍
*/
ll really[100010]; 
int main()
{
	int N;
	cin >> N;  //共有N個test cases
	while (N--)
	{
		int n;
		scanf("%d", &n);
		bool buxing = false; //“不行”的拼音，一旦為true就說明這組樣例“不行”
		map<ll, int> ma; //用map記錄出現了幾次（條件一）
		for (int i = 0; i < 2 * n; i++)
		{
			ll t;
			scanf("%lld", &t);
			if (t % 2) //差值和是否為偶數（條件二）
				buxing = 1; //如果t%2有余數，則說明這個數是奇數
			ma[t]++; //t出現的次數加一
		}
		int sum = 1; //really陣列中需要放置的數的下標，筆者選擇從下標1開始存放
		ll realOriSum = 0; // 這是計算出來的原陣列中的數，上文樣例中便是 9  7  3
		/*ma的迭代器，這個for回圈從小到大遍歷了插入ma中的差值和*/
		for (map<ll, int>::iterator it = ma.begin(); it != ma.end(); it++)
		{
			/*it->second就是這個差值和出現的次數*/
			if (it->second != 2) // 差值和是否都出現了兩處（條件一）
				buxing = 1;
			/*it->first是這個差值和*/
			really[sum++] = (it->first) / 2; // 差值和的一半存放到really陣列中
		}
		for (sum--; sum > 0; sum--)
		{
			ll all = really[sum] - realOriSum; //減去原來的數
			if (all % sum)	//是否可以整除
				buxing = 1;
			ll thisReal = all / sum; // 這個是原始陣列（計算差值和之前那個±2±7±9的陣列）
			realOriSum += thisReal; // 求出的原始的數的和
			if (thisReal <= 0)  // 按上述方法，原來的數必須是正數
				buxing = 1;
		}
		if (buxing) //如果不行buxing就會為true，這個樣例從頭到尾都可以，buxing就還是原來初始的false
			puts("NO");
		else //否則就可以
			puts("YES");
	}
	return 0;
}

結語

打競賽需要能夠靜下心來思考，
重在思路，次在代碼具體實作，
代碼能不能看懂不重要，思路想明白了才是最重要的，
如有錯誤，歡迎指正，您的批評將是我前進的動力，
加油加油~

寫到凌晨兩點不容易，喜歡了就點個贊再走叭