CodeForces - 1343B - Balanced Array

tech2022-09-11  88

链接:https://codeforces.com/problemset/problem/1343/B

原题

You are given a positive integer nn, it is guaranteed that nn is even (i.e. divisible by 22). You want to construct the array aa of length nn such that:

The first n2n2 elements of aa are even (divisible by 22); the second n2n2 elements of aa are odd (not divisible by 22); all elements of aa are distinct and positive; the sum of the first half equals to the sum of the second half (∑i=1n2ai=∑i=n2+1nai∑i=1n2ai=∑i=n2+1nai).

If there are multiple answers, you can print any. It is not guaranteed that the answer exists. You have to answer tt independent test cases.

Input The first line of the input contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases. Then tt test cases follow. The only line of the test case contains one integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the length of the array. It is guaranteed that that nn is even (i.e. divisible by 22). It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105 (∑n≤2⋅105∑n≤2⋅105). Output For each test case, print the answer — “NO” (without quotes), if there is no suitable answer for the given test case or “YES” in the first line and any suitable array a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) satisfying conditions from the problem statement on the second line.

Example

Input 5 2 4 6 8 10

Output NO YES 2 4 1 5 NO YES 2 4 6 8 1 3 5 11 NO

题意

给一个n(n要能被2整除),作为一个数组的长度,数组的前n/2个数都是偶数,后半段都是奇数,且所有数都不相同。前半段之和等于后半段之和。 输入一个n,若能满足以上条件,输出YES并输出一个可能的数组;若不能则输出NO。

思路

首先分析当n/2为奇数时, 前半段:奇数个偶数相加为偶数;后半段:奇数个奇数相加为奇数。所以前后不可能相等。 所以n/2只能是偶数时才满足题意,所以n必须被4整除。 前半段输出2,4,6,8,……,2k (k=1,2,3,……,n/2) 后半段输出1,3,5,7,…… 最后一个数输出3k-1即可。

代码

#include<iostream> using namespace std; int t; int main() { int n; cin>>t; while(t--) { cin>>n; if(n%4!=0) cout<<"NO"<<endl; else { cout<<"YES"<<endl; for(int i=1;i<=n/2;i++) cout<<2*i<<" "; for(int i=1;i<n/2;i++) cout<<2*i-1<<" "; cout<<n/2*3-1<<endl; } } return 0; }
最新回复(0)