题解 | #构造数列#

题目链接

构造数列

题目描述

给定一个偶数 $n$ ，需要构造一个长度为 $n$ 的、由互不相同的正整数组成的数组。该数组需要满足以下条件：

前 $n/2$ 个数是偶数。
后 $n/2$ 个数是奇数。
前 $n/2$ 个数的和等于后 $n/2$ 个数的和。

如果存在这样的数组，输出 YES 并给出任意一个解；否则输出 NO。

解题思路

设数组的长度为 $n$ ，则偶数和奇数各有 $m=n/2$ 个。

$m$ 个偶数之和永远是偶数。
$m$ 个奇数之和的奇偶性与 $m$ 相同。
要使两边的和相等，它们的奇偶性必须相同。因此，奇数部分的和必须是偶数，这意味着 $m$ 必须是偶数。

所以，只有当 $m=n/2$ 是偶数时，即 $n$ 是 $4$ 的倍数时，问题才可能有解。当 $n/2$ 是奇数时，问题无解。

对于 $n$ 是 $4$ 的倍数的情况，我们可以构造一个解：

偶数部分：我们选择最简单、最小的 $m$ 个正偶数： $2, 4, 6, \dots, 2m$ 。其和为 $\sum_{i=1}^{m} 2i = 2 \cdot \frac{m(m+1)}{2} = m(m+1)$ 。
奇数部分：我们先选择最小的 $m-1$ 个正奇数： $1, 3, 5, \dots, 2m-3$ 。其和为 $\sum_{i=1}^{m-1} (2i-1) = (m-1)^2$ 。
最后一个奇数 $o_m$ 就由总和的差值来确定： $o_m = (\text{偶数总和}) - (\text{前 } m-1 \text{ 个奇数总和}) = m(m+1) - (m-1)^2 = 3m-1$ 。

构造的有效性：

我们构造的偶数是 $2, 4, \dots, 2m$ 。
构造的奇数是 $1, 3, \dots, 2m-3$ 以及 $3m-1$ 。
由于 $m \ge 2$ (因为 $n$ 是4的倍数)， $3m-1 > 2m-3$ ，所以最后一个奇数与之前的奇数不重复。所有数字都是正整数且互不相同。

因此，这个构造是有效的。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

void solve() {
    int n;
    cin >> n;
    int m = n / 2;
    if (m % 2 != 0) {
        cout << "NO\n";
        return;
    }

    cout << "YES\n";
    long long even_sum = 0;
    // 构造并输出 n/2 个偶数
    for (int i = 1; i <= m; ++i) {
        long long val = 2LL * i;
        cout << val << " ";
        even_sum += val;
    }
    
    long long odd_sum = 0;
    // 构造并输出 n/2 - 1 个奇数
    for (int i = 1; i < m; ++i) {
        long long val = 2LL * i - 1;
        cout << val << " ";
        odd_sum += val;
    }

    // 输出最后一个奇数
    cout << even_sum - odd_sum << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

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) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        int m = n / 2;
        if (m % 2 != 0) {
            System.out.println("NO");
            return;
        }

        System.out.println("YES");
        long evenSum = 0;
        // 构造并输出 n/2 个偶数
        for (int i = 1; i <= m; i++) {
            long val = 2L * i;
            System.out.print(val + " ");
            evenSum += val;
        }
        
        long oddSum = 0;
        // 构造并输出 n/2 - 1 个奇数
        for (int i = 1; i < m; i++) {
            long val = 2L * i - 1;
            System.out.print(val + " ");
            oddSum += val;
        }

        // 输出最后一个奇数
        System.out.println(evenSum - oddSum);
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    m = n // 2
    if m % 2 != 0:
        print("NO")
        return

    print("YES")
    evens = [2 * i for i in range(1, m + 1)]
    odds = [2 * i - 1 for i in range(1, m)]
    
    last_odd = sum(evens) - sum(odds)
    
    result = evens + odds + [last_odd]
    print(*result)


t = int(sys.stdin.readline())
for _ in range(t):
    solve()

算法及复杂度

算法：数学构造
时间复杂度： $\mathcal{O}(n)$ ，对于每组测试数据，我们需要构造并输出一个长度为 $n$ 的数组。
空间复杂度： $\mathcal{O}(n)$ ，在Python版本中需要存储构造的数组，C++/Java版本可以优化到 $\mathcal{O}(1)$ 。