构造数列【牛客tracker 每日一题】
构造数列
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
给定一个正整数n nn，保证n nn为偶数。请构造一个长度为n nn的整数数组 {a 1 , a 2 , … , a n a_1,a_2,…,a_na1,a2,…,an} ，使其满足如下条件：
- 前n 2 \frac{n}{2}2n个数全部为偶数；
- 后n 2 \frac{n}{2}2n个数全部为奇数；
- 前n 2 \frac{n}{2}2n个数的元素之和等于后n 2 \frac{n}{2}2n 个数的元素之和；
- 对任意1 ≦ i < j ≦ n 1≦i<j≦n1≦i<j≦n，均满足a i ≠ a j a_i≠a_jai=aj。
如果存在满足条件的数组，请给出任意一组答案；否则，请说明不存在。
名词解释
- ∙偶数：可以表示为2 k ( k ∈ Z ) 2k (k∈Z)2k(k∈Z)的整数。
- 奇数：可以表示为2 k + 1 ( k ∈ Z ) 2k+1 (k∈Z)2k+1(k∈Z)的整数。
输入描述：
每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≦ T ≦ 10 4 ) T(1≦T≦10^4)T(1≦T≦104)代表数据组数，每组测试数据描述如下：
- 在一行上输入一个整数n ( 2 ≦ n ≦ 2 × 10 5 ) n(2≦n≦2×10^5)n(2≦n≦2×105)表示数组的长度。保证n nn为偶数。
除此之外，保证单个测试文件的n nn之和不超过2 × 10 5 2×10^52×105。
输出描述：
对于每一组测试数据：
- 若不存在满足条件的数组，在一行上输出N O NONO；
- 若存在满足条件的数组，先在一行上输出Y E S YESYES，再在下一行输出一个满足条件的数组a 1 , a 2 , … , a n ( 1 ≦ a i ≦ 10 9 ) a_1,a_2,…,a_n (1≦a_i≦10^9)a1,a2,…,an(1≦ai≦109)，相邻两个数之间使用空格分隔。
示例1
输入：
5 2 4 6 8 10输出：
NO YES 2 4 1 5 NO YES 2 4 6 8 1 3 5 11 NO示例2
输入：
2 4 2输出：
YES 2 4 1 5 NO说明：
在第一个样例中：
- n = 4 n=4n=4，前半部分长度为2 22，取两个不同的偶数2 , 4 2,42,4；
- 后半部分长度为2 22，取两个不同的奇数1 , 5 1,51,5；
- 2 + 4 = 1 + 5 = 6 2+4=1+5=62+4=1+5=6，且所有元素互不相同，因此满足条件。
在第二个样例中，当n = 2 n=2n=2时无法同时满足和相等与互不相同的要求，故答案不存在。
解题思路
首先判断n / 2 n/2n/2是否为奇数，若是则输出N O NONO（前半部分偶数之和必为偶数，后半部分奇数个数为奇数时和为奇数，无法相等）；若n / 2 n/2n/2为偶数则可构造数组，前n / 2 n/2n/2个元素取连续不同偶数（ 2 、 4 、 … 、 n ） （2、4、…、n）（2、4、…、n），保证均为偶数且互不相同，前半部分和为( 2 + n ) ∗ n / 4 (2+n)*n/4(2+n)∗n/4；后半部分前n / 2 − 1 n/2-1n/2−1个元素取连续不同奇数（ 1 、 3 、 … 、 n − 1 ） （1、3、…、n-1）（1、3、…、n−1），最后一个奇数调整为( 2 ∗ ( n / 2 ) − 1 ) + n / 2 (2*(n/2)-1)+n/2(2∗(n/2)−1)+n/2，使后半部分和等于前半部分，且所有元素互不相同；该方法通过奇偶性分析快速判定是否可构造，构造时用连续奇偶数列保证唯一性，时间复杂度O ( n ) O(n)O(n)，适配T TT达1 e 4 、 ∑ n ≤ 2 e 5 1e4、∑n≤2e51e4、∑n≤2e5的规模，高效输出符合条件的数组或判定不存在。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=2e5+10;voidsolve(){ll n;cin>>n;if((n/2)%2==1){cout<<"NO\n";return;}vector<ll>a(n);cout<<"YES\n";for(ll i=1;i<=n/2;++i)cout<<i*2<<" ";for(ll i=1;i<=n/2;++i){if(i!=n/2)cout<<i*2-1<<" ";elsecout<<2*i-1+n/2<<"\n";}}intmain(){ll t;cin>>t;while(t--)solve();return0;}