Codeforces C. Nezzar and Symmetric Array (#698 Div.2) (构造 / 思维)

本文主要是介绍Codeforces C. Nezzar and Symmetric Array (#698 Div.2) (构造 / 思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

题意： 有一个数组a，由2n个不同的整数组成，对于每个 $a_{i}$ 都有一个 $a_{j}$ 使得 $a_{i}$ = − $a_{j}$ (1<=i,j<=2n)。

有一结果数组d，其 $d_{i}$ = $\sum _{j=1}^{2n}|a_{i}-a_{j}|$ ，现在给出这个数组d，能否找到对应的数组a。

思路：

* 由于是找对称点，可以放在数轴上来讨论。 $a_{i}$ 为数轴上的点， $d_{i}$ 为其与其他所有点的距离和。

* 不难发现，d值大的点在两侧，d值小的点在中间。由于是对称的，我们讨论一边即可。

* 不难发现： $a_{i-1}$ 与 $a_{i}$ 间的距离 $x_{i}$ = | $a_{i-1}$ - $a_{i}$ |。

$d_{i}$ = ( ( $a_{i-1}$ 点到其左侧所有点的距离和) + (n+i-1)* $x_{i}$ ) + ( $a_{i}$ 到其右侧所有点的距离和)。

$d_{i-1}$ = ( $a_{i-1}$ 点到其左侧所有点的距离和) + ( (n-i+1) $x_{i}$ + ( $a_{i}$ 到其右侧所有点的距离和) )。

因此 $d_{i}$ = (2*n-2)* $x_{i}$ ，若求得的 $x_{i}$ 不为整数，则不存在数组a。

* 现在我们确定了所有点都能找到对称点了，开始判断它们的对称距离是否为偶数，即是否能正好关于0点对称。

即得满足 $x_{1}$ = 2* $a_{1}$ ，而 $d_{1}$ = n* $x_{1}$ + 2*( $a_{1}$ 到其右侧所有点的距离和)，求得的 $x_{1}$ 必须为大于0的偶数。

* 满足以上所有条件，则能够构成合法的a数组，思路有参考大佬博客。

代码实现：

#include<bits/stdc++.h>
#define endl '\n'
#define null NULL
#define ll long long
#define int long long
#define pii pair<int, int>
#define lowbit(x) (x &(-x))
#define ls(x) x<<1
#define rs(x) (x<<1+1)
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
using namespace std;
const int  inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-6;
const ll   mod = 1e9 + 7;
const int  N = 2e5 + 5;inline void read(int &x){char t=getchar();while(!isdigit(t)) t=getchar();for(x=t^48,t=getchar();isdigit(t);t=getchar()) x=x*10+(t^48);
}int t, n;
int d[N], st[N]; //用来存放a1-an的到其他点的距离和
map<int,int> mp;signed main ()
{IOS;cin >> t;while(t --){mp.clear();cin >> n;int cnt = 0, m = n<<1;for(int i = 0; i < m; i ++){cin >> d[i];mp[d[i]] ++;if(mp[d[i]]==1) st[++cnt] = d[i];}sort(st+1, st+cnt+1);int flag = 0;for(int i = 1; i <= cnt; i++){if(mp[st[i]]!=2){ //确保每个点a[i]都能有个和它对称的点a[j]flag = 1;     //但目前还不能确定对称距离是否为偶数break;        //即不能确定是 -1 1 这样的对称, 还是 -1 2这样的对称}}int sum = 0; //用来求a1到右边所有点的距离和if(!flag){for(int i = cnt; i > 1; i --){int k = 2*i-2;int s = st[i]-st[i-1];if(s%k){  //xi不是整数flag = 1;break;}else sum += (cnt-i+1)*(s/k);}}   //实际d1太小      //x1不是整数       //x1为奇数,不能关于0点对称if((st[1]-2*sum)<=0 || (st[1]-2*sum)%n || (st[1]-2*sum)/n%2) flag = 1; //判断x1是否能存在cout << (flag ? "NO":"YES") << endl;}return 0;
}

这篇关于Codeforces C. Nezzar and Symmetric Array (#698 Div.2) (构造 / 思维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！