C.Nezzar and Symmetric Array
生肉{:target=”_blank”}
题目翻译
很久以前,有个对称的数组 $a _ 1, a _ 2, \cdots, a _ {2n}$,包含 $2n$ 个互不相同的整数。
在数组 $a _ 1, a _ 2, \cdots, a _ {2n}$ 中,如果对于每个 $1 \leq i \leq 2n$,都存在 $1 \leq j \leq 2n$,使得 $a _ i = - a _ j$,则称 $a$ 是对称的。
对于 $1 \leq i \leq 2n$,$\text {Nezzar}$ 记录了 $\begin {aligned} d _ i = \sum _ {j = 1} ^ {2n} |a _ i - a _ j| \end {aligned}$
$\text {Nezzar}$ 记录了 $d$ 后遗忘了 $a$。现在 $\text {Nezzar}$ 想知道,是否存在 $a$,使得 $d$ 满足上述条件。
输入
第一行包含一个正整数 $t \ (1 \leq t \leq 10 ^ 5)$,表示测试数据组数。
对于每组测试数据:
第一行包含一个整数 $n \ (1 \leq n \leq 10 ^ 5)$。
第二行包含 $2n$ 个正整数 $d _ 1, d _ 2, \cdots, d _ {2 n} \ (0 \leq d _ i \leq 10 ^ {12})$。
数据保证所有 $n$ 的和不超过 $10 ^ 5$。
输出
对于每组测试数据,如果 $a$ 存在,则输出 YES
,否则输出 NO
。
样例输入
6
2
8 12 8 12
2
7 7 9 11
2
7 11 7 11
1
1 1
4
40 56 48 40 80 56 80 48
6
240 154 210 162 174 154 186 240 174 186 162 210
样例输出
YES
NO
NO
NO
NO
YES
算法
(推式子) $O(n)$
首先不难发现一个性质:如果我们改变 $a$ 中元素的顺序,那么 $d$ 中元素的顺序也会相应改变。
那么不妨假设 $a$ 已经按升序排序,考虑此时 $d$ 的顺序。
因为 $a$ 已经按升序排序了,并且 $a$ 是对称的,所以 $a _ 1 < a _ 2 < \cdots < a _ n < 0 < a _ {n + 1} < \cdots < a _ {2 n}$。
并且 $a _ i = - a _ {2n - i + 1}, d _ i = d _ {2n - i + 1}$。
那么我们只需要考虑 $1 \leq i \leq n$ 或者 $n < i \leq 2n$ 的 $a _ i$ 和 $d _ i$ 即可。
下文中仅考虑 $n < i \leq 2n$ 的情况。
我们可以将 $a$ 画在一个数轴上,那么 $d _ i$ 表示的意义就是 $a _ i$ 与其它数的距离之和。
(图中除 $0$ 外所有绿点即为 $a$)
考虑此时的 $a _ i$ 和 $a _ {i + 1}$,上图中橙线的长度即为 $d _ i$,蓝(深蓝)线长度为 $d _ {i + 1}$。
不难发现,除 $a _ i \sim a _ {i + 1}$ 这段外,其它段的线段数量相等,那么其他段的和也就相等。
所以 $d _ {i + 1} - d _ i$ 一定是 $a _ {i + 1} - a _ i$ 的某倍数,即 $d _ {i + 1} - d _ i = k(a _ {i + 1} - a _ i)$。
考虑 $a _ {i + 1}$ 向左边 $i$ 条线,$a _ i$ 向右边连了 $2n - i$ 条线。
而 $a _ {i + 1}$ 每向左边连一条线,就将 $a _ i \sim a _ {i + 1}$ 这段多覆盖一次。
同理 $a _ i$ 每向右边连一条线,就将 $a _ i \sim a _ {i + 1}$ 这段多覆盖一次。
因为 $i > n$,所以 $i > 2n - i$,这说明 $d _ i < d _ {i + 1}$,那么 $d$ 的顺序就是从小到大排序。
并且 $a _ i \sim a _ {i + 1}$ 被覆盖的次数,就是 $i - (2n - i) = 2i - 2n$,即 $d _ {i + 1} - d _ i = (2i - 2n) (a _ {i + 1} - a _ i)$。
那么我们就可以按顺序求出来每个 $a _ {i + 1} - a _ i$。
但这样我们只求出来了相对位置,没有求出 $a$ 的绝对位置。
要求 $a$ 的绝对位置,我们只需固定住一个 $a _ i$ 即可。
不妨固定住 $a _ {n + 1}$(因为我们是从 $a _ {n + 1}$ 开始计算的)。
考虑 $a _ {n + 1}$ 会向左边连 $n$ 条线(每个点都连一次)。
那么我们计算出前面所有 $a _ {i + 1} - a _ i$ 后,可以用这些信息求出 $a _ n 到 a _ {n + 1}$ 的距离。
并且我们知道 $a _ n = - a _ {n + 1}$,那么我们就可以求出 $a _ {n + 1}$ 的绝对位置了。
剩下的就是根据题意一顿判断。具体可见代码注释。
时间复杂度
$O(n)$,具体可见代码。
C++ 代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 200005;
int task, n;
ll d[N], a[N];
int main()
{
scanf("%d", &task);
while (task -- )
{
scanf("%d", &n), n <<= 1;
for (int i = 1; i <= n; i ++ ) scanf("%lld ", d + i);
sort(d + 1, d + n + 1);
bool yes = true;
for (int i = 1; i <= n; i += 2) // 如果不是成对出现,则不合法。
if (d[i] != d[i + 1])
{
yes = false;
break;
}
if (!yes) {puts("NO"); continue;}
n >>= 1;
for (int i = 1; i <= n; i ++ ) d[i] = d[i << 1];
ll s = 0; // 计算上文中 a[n + 1] 连到 a[n] 左边的线段总长。
for (int i = 1; i < n && yes; i ++ )
{
a[i] = d[i + 1] - d[i];
if (!a[i]) yes = false; // 题目中规定 a[i] 不相等,即 d[i + 1] - d[i] != 0。
else if (a[i] % (2 * i)) yes = false; // 因为我们是从 1 开始枚举的 i,所以上文中的 2i - 2n 就是 2i。
a[i] /= 2 * i; // 注意此处的 a[i] 存的是上文中的 a[i + 1] - a[i]。
s += a[i] * (n - i); // 将 a[i + 1] - a[i] 对称到左边,由图可知 a[n + 1] 向左边连了 n - i 条线。
}
if (!yes) puts("NO");
// a[n] ~ a[n + 1] 被 d[n + 1] 覆盖了 n 次,
// 并且因为 a[n] = -a[n + 1],所以 a[n + 1] - a[n] % 2 为 0,
// 所以 (d[n + 1] - 2s) 应该是 2n 的倍数,若不是,则不合法。
else if ((d[1] - 2 * s) % (2 * n)) puts("NO");
// 如果 a[n + 1] 在 0 的位置或 0 的左边,则不合法。
else if (d[1] <= 2 * s) puts("NO");
else puts("YES");
}
return 0;
}
抽风姐姐用心了