题解

题目描述

给定正整数 $n,k$，要求构造长度为 $n$ 的排列 $p$（即包含 $1$～$n$ 的每个数恰好一次），定义数组
$a_i$ =|$p_{i+1}$ - $p_i$|,($1$$\le$ $i$$\le$ $n-1$).
如果数组 $a$ 是公差为 $k$ 的等差数列，就称 $p$ 是一个“好排列”。
输出任意一个好排列，若不存在则输出 NO。

思路概述

1. 分析差值序列的取值范围

   • 差值 $a_i$ 必须满足 $1\le a_i \le n-1$。
   • 设等差数列首项为 $A$，公差为 $k$，共有 $n-1$ 项，则$$a_i = A + (i-1)\,k,\quad i=1,2,\dots,n-1.$$
   • 要保证对所有 $i$，都有 $1\le A+(i-1)k\le n-1$。
   • 解得只有三种可能的 $k$：$$k = -1,\quad k=0,\quad k=1.$$

2. 三种情况分别构造

   • $k=0$：所有差值都相同。取最简单的 $a_i\equiv1$，令 $p=[1,2,\dots,n]$，则差值序列全为 $1$，公差 $0$。
   • $k=-1$：需要差值序列 $a_i=n-1,n-2,\dots,1$。可以令$$p = [1,n,2,n-1,3,n-2,\dots]$$ 即交替从两端取数。验证可得 $a_i$ = |$p_{i+1}$-$p_i$| = $n$ - $i$,$i=1,2,\dots,n-1,$ 正好首项 $A=n-1$，公差 $-1$。
   • $k=1$：需要差值序列 $a_i=1,2,\dots,n-1$。只需将上述 $k=-1$ 的排列取逆序即可。

若 $k\notin\{-1,0,1\}$，则不存在满足条件的排列，直接输出 NO。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, k;
    cin >> n >> k;

    if (k == 0) {
        // k=0 时，直接输出 1..n
        cout << "YES\n";
        for (int i = 1; i <= n; i++) {
            cout << i << (i == n ? '\n' : ' ');
        }
    }
    else if (k == -1) {
        // k=-1 时，交替从两端取数，构造差值 n-1, n-2, ...,1
        cout << "YES\n";
        int L = 1, R = n;
        for (int i = 1; i <= n; i++) {
            if (i & 1) {
                cout << L++;
            } else {
                cout << R--;
            }
            cout << (i == n ? '\n' : ' ');
        }
    }
    else if (k == 1) {
        // k=1 时，先按照 k=-1 构造，再逆序
        vector<int> p;
        int L = 1, R = n;
        for (int i = 1; i <= n; i++) {
            if (i & 1) p.push_back(L++);
            else       p.push_back(R--);
        }
        reverse(p.begin(), p.end());
        cout << "YES\n";
        for (int i = 0; i < n; i++) {
            cout << p[i] << (i+1 == n ? '\n' : ' ');
        }
    }
    else {
        // 其他 k 无解
        cout << "NO\n";
    }

    return 0;
}

Python

# -*- coding: utf-8 -*-
import sys

def main():
    data = sys.stdin.read().strip().split()
    n, k = map(int, data)

    if k == 0:
        # k=0，输出升序
        print("YES")
        print(*range(1, n+1))
    elif k == -1:
        # k=-1，交替出两端
        print("YES")
        L, R = 1, n
        res = []
        for i in range(1, n+1):
            if i % 2 == 1:
                res.append(L)
                L += 1
            else:
                res.append(R)
                R -= 1
        print(*res)
    elif k == 1:
        # k=1，先构造 k=-1，再逆序
        L, R = 1, n
        res = []
        for i in range(1, n+1):
            if i % 2 == 1:
                res.append(L)
                L += 1
            else:
                res.append(R)
                R -= 1
        res.reverse()
        print("YES")
        print(*res)
    else:
        # 其他情况无解
        print("NO")

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        br.close();

        if (k == 0) {
            // k=0，输出 1..n
            System.out.println("YES");
            for (int i = 1; i <= n; i++) {
                System.out.print(i + (i == n ? "\n" : " "));
            }
        } else if (k == -1) {
            // k=-1，交替取两端
            System.out.println("YES");
            int L = 1, R = n;
            for (int i = 1; i <= n; i++) {
                if ((i & 1) == 1) {
                    System.out.print(L++);
                } else {
                    System.out.print(R--);
                }
                System.out.print(i == n ? "\n" : " ");
            }
        } else if (k == 1) {
            // k=1，先构造 k=-1，再逆序
            List<Integer> p = new ArrayList<>();
            int L = 1, R = n;
            for (int i = 1; i <= n; i++) {
                if ((i & 1) == 1) {
                    p.add(L++);
                } else {
                    p.add(R--);
                }
            }
            Collections.reverse(p);
            System.out.println("YES");
            for (int i = 0; i < n; i++) {
                System.out.print(p.get(i) + (i+1 == n ? "\n" : " "));
            }
        } else {
            // 其他 k 无解
            System.out.println("NO");
        }
    }
}

题目内容

对于一个排列$p$，其下标从$1$开始，通过以下规则得到长度为$n-1$的数组$a$。

换句话说，即$a_i=|p_{i+1} -p_i|$。

若满足数组$a$是一个公差为k的等差数列，我们则称$p$是一个好排列。

现在小红给你整数$n,k$，请你帮助他构造一个好排列。

长度为$n$ 的排列是由$1$~$n$这$n$个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，{$2,3, 1, 5,4$}是一个长度为$5$的排列，而{$1, 2, 2$} 和{$1, 3,4$} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述

一行两个整数$n,k(4≤n≤2×10^5,-n<k<n)$，表示排列的长度和公差。

输出描述

若存在满足条件的排列，第一行输出"$YES$",第二行输出$n$个整数，每个整数用空格隔开，表示满足条件的排列，若不存在则输出"$NO$"。

样例1

输入

4 -1

输出

YES
1 4 2 3

说明

$a_1=|p_2-p_1|=3$

$a_2 = |p_3 - p_2| =2$

$a_3=|p_4-p_3| =1$

故$a = 3,2,1$，其公差为$-1$，符合题意。

样例2

输入

6 4

输出

NO