首页 > 试题广场 >

构造数列

[编程题]构造数列
  • 热度指数:217 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个正整数 n,保证 n 为偶数。请构造一个长度为 n 的整数数组 \{a_1, a_2, \dots, a_n\},使其满足如下条件:
\hspace{23pt}\bullet\,\tfrac{n}{2} 个数全部为偶数;
\hspace{23pt}\bullet\,\tfrac{n}{2} 个数全部为奇数;
\hspace{23pt}\bullet\,\tfrac{n}{2} 个数的元素之和等于后 \tfrac{n}{2} 个数的元素之和;
\hspace{23pt}\bullet\,对任意 1 \leqq i \lt j \leqq n,均满足 a_i \neq a_j

\hspace{15pt}如果存在满足条件的数组,请给出任意一组答案;否则,请说明不存在。

\hspace{15pt}名词解释
\hspace{23pt}\bullet\,偶数:可以表示为 2k\ (k\in\mathbb{Z}) 的整数。
\hspace{23pt}\bullet\,奇数:可以表示为 2k+1\ (k\in\mathbb{Z}) 的整数。

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 10^4\right) 代表数据组数,每组测试数据描述如下: 
\hspace{23pt}\bullet\,在一行上输入一个整数 n\left(2\leqq n\leqq 2\times10^5\right) 表示数组的长度。保证 n 为偶数。
\hspace{15pt}除此之外,保证单个测试文件的 n 之和不超过 2\times10^5


输出描述:
\hspace{15pt}对于每一组测试数据: 
\hspace{23pt}\bullet\,若不存在满足条件的数组,在一行上输出 \texttt{NO}
\hspace{23pt}\bullet\,若存在满足条件的数组,先在一行上输出 \texttt{YES},再在下一行输出一个满足条件的数组 a_1, a_2, \dots, a_n\ \left(1\leqq a_i \leqq 10^9\right),相邻两个数之间使用空格分隔。
示例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

说明

\hspace{15pt}在第一个样例中: 
\hspace{23pt}\bullet\,n=4,前半部分长度为 2,取两个不同的偶数 2,4
\hspace{23pt}\bullet\,后半部分长度为 2,取两个不同的奇数 1,5
\hspace{23pt}\bullet\,2+4=1+5=6,且所有元素互不相同,因此满足条件。
\hspace{15pt}在第二个样例中,当 n=2 时无法同时满足和相等与互不相同的要求,故答案不存在。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 读取测试用例数

        while (T-- > 0) {
            int n = sc.nextInt();
            if (n % 4 != 0) {
                // n是2的倍数但非4的倍数,无法满足条件
                System.out.println("NO");
                continue;
            }

            System.out.println("YES");
            int m = n / 2;
            int[] arr = new int[n];

            // 1. 构造前半段:连续偶数(2, 4, ..., 2m)
            for (int i = 0; i < m; i++) {
                arr[i] = 2 * (i + 1);
            }

            // 2. 构造后半段:前m-1个连续奇数,最后1个补全和
            int sumEven = m * (m + 1); // 前半段和(公式:2+4+...+2m = m(m+1))
            int sumOdd = 0;
            for (int i = 0; i < m - 1; i++) {
                arr[m + i] = 2 * i + 1; // 连续奇数:1, 3, 5...
                sumOdd += arr[m + i];
            }
            arr[n - 1] = sumEven - sumOdd; // 最后一个奇数,确保两段和相等

            // 输出数组
            for (int num : arr) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
        sc.close();
    }
}

发表于 2025-10-16 18:04:12 回复(0)