Codeforces Round #698 Nezzar and Symmetric Array 构造

题意

给你一个n。现在假设一个长度为2n的数组a,且这个数组a中对于任意的$a_i$一定存在一个j使得$a_i=-a_j$,且a中没有重复数字。根据a,得到一个长度为2n的数组d。其中$d_i=\sum_{j=1}^{2n}\mid{a_i-a_j}\mid$。现在给你这个d,问你a是否是可能的。

题解

首先观察任意两个数,$a_i$和$a_j$。根据题意立刻可知,a中存在$-a_i$和$-a_j$。所以没有必要考虑符号,直接假设$a_i>0,\ a_j>0$。

考量$\mid{a_i-a_j}\mid+\mid{a_i-(-a_j)}\mid$可知:如果$a_i>a_j$则这个和为$2a_i$,反之则为$2a_j$。

于是可以得知,对于d,d中最大的那个,一定是由a中最大的那个。且$d_i={2}{n}{a_i}$。同理,可依次推至第二大的,第三大的。于是就可以通过d构造回a的正数部分。

需要注意的是,这样构造出来的是正数部分,如果是负数,则失败。且构造出来的数不应该有重复。

代码

Submission #111835021 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论