Nezzar and Symmetric Array
题意
思路
举个例子−4,−3,−2,−1,1,2,3,4 可以发现规律 ：一个数到一个较小的数和这个较小的数的相反数的距离是自身的两倍 比如 4 到 -3 和 4 到 3 距离为 8
并且一个绝对值较小的数和两个绝对值比它大的正负数的距离和 = 二倍大数的绝对值
所以可以从大到小考虑依次还原数组 判断是否符合条件即可又发现了一个规律
首先记录d数组中每个数出现的次数 稍微想一下可以知道 一个数肯定是两个两个出现 并且是偶数
用 sum 记录 当前数到比它绝对值大的数的距离t.first 减去sum 后得到的为 当前数到所有绝对值小于等于自己的数（这样的数有n个 每次找到后 n–）的距离 可以得到 x= (t.first−sum)/ 2 / n
记录上一个找到的数为las 因为是从大到小找且找正的那个 所以 如果x>=las ∣∣ x<=0 就不合题意了
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f //#define mod 1000000007 using namespace std; typedef long long LL; typedef pair<int, int>PII; inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } const int N = 200010; int n; LL a[N]; bool cmp(LL a, LL b) { return a > b; } void solve() { bool flag = true; cin >> n; map<LL, LL, greater<LL>>mp; for (int i = 1; i <= 2 * n; ++i) { cin >> a[i]; mp[a[i]]++; } LL las = LLONG_MAX; LL sum = 0; for (auto &t : mp) { //cout << "t.first == " << t.first << endl; if (t.second != 2) { flag = false; break; } else if (t.first & 1) { flag = false; break; } else { if (((t.first - sum) / 2) % n) { flag = false; break; } LL x = (t.first - sum)/ 2 / n; //cout << "x == " << x << endl; if (x <= 0 || x >= las) { flag = false; break; } n--; sum += 2 * x; las = x; } } if (flag)puts("YES"); else puts("NO"); } int main() { int t; cin >> t; while (t--) solve(); return 0; }
