解题思路

核心想法（简单构造） 把区间 [1, 2, ..., k+1] 整体倒序，其余 [k+2, k+3, ..., n] 仍按升序接在后面，即：

[k+1, k, k-1, ..., 2, 1, k+2, k+3, ..., n]

• 在前半段倒序的长度为 k+1 的块里，恰好产生 k 个相邻逆序对（每一对相邻元素都满足前者大于后者）。
• 连接点是 1 与 k+2，此处为上升（不会多出逆序对）。
• 后半段严格升序，不再产生新的相邻逆序对。 因此相邻逆序对总数正好为 k，并且用到了 1..n 各一次，合法为排列。

相关算法 这是一个构造法（Construction），可视作“贪心地一次性制造 k 个相邻逆序对”的做法。无需搜索或复杂数据结构。

实现方法

1. 输出 k+1, k, ..., 1。
2. 再输出 k+2, k+3, ..., n。 时间与空间都线性。

复杂度分析

• 时间复杂度：O(n)（顺序生成并输出每个数一次）。
• 空间复杂度：O(1) 额外空间（若直接流式输出；若存数组再输出则为 O(n)）。

代码实现

Python

# 题意：构造一个 1..n 的排列，使得相邻逆序对（a[i] > a[i+1]）恰好为 k
# 构造：把 [1..k+1] 倒序，后接 [k+2..n]

import sys

def construct_permutation(n, k):
    # 前半段倒序制造恰好 k 个相邻逆序
    ans = list(range(k + 1, 0, -1))
    # 后半段保持升序，不再引入逆序
    ans += list(range(k + 2, n + 1))
    return ans

def main():
    data = sys.stdin.readline().strip().split()
    n, k = map(int, data)
    res = construct_permutation(n, k)
    print(" ".join(map(str, res)))

if __name__ == "__main__":
    main()

Java

// 题意：构造一个 1..n 的排列，使得相邻逆序对数为 k
// 思路：先输出 k+1..1（倒序），再输出 k+2..n（升序）

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

public class Main {
    // 构造函数：返回合法排列
    static int[] constructPermutation(int n, int k) {
        int[] a = new int[n];
        int idx = 0;
        // 前半段倒序：k+1, k, ..., 1
        for (int x = k + 1; x >= 1; x--) {
            a[idx++] = x;
        }
        // 后半段升序：k+2, ..., n
        for (int x = k + 2; x <= n; x++) {
            a[idx++] = x;
        }
        return a;
    }

    public static void main(String[] args) throws Exception {
        // 根据数据范围，使用 BufferedReader + StringTokenizer 读入更高效
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] ans = constructPermutation(n, k);

        // 输出结果
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ans.length; i++) {
            if (i > 0) sb.append(' ');
            sb.append(ans[i]);
        }
        System.out.println(sb.toString());
    }
}

C++

// 题意：构造一个 1..n 的排列，使得相邻逆序对数量为 k
// 构造法：把 [1..k+1] 倒序（产生 k 个相邻逆序），再接 [k+2..n] 升序（不增加逆序）

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

// 构造函数：返回合法排列
vector<int> constructPermutation(int n, int k) {
    vector<int> a;
    a.reserve(n);
    // 前半段倒序：k+1, k, ..., 1
    for (int x = k + 1; x >= 1; --x) {
        a.push_back(x);
    }
    // 后半段升序：k+2, ..., n
    for (int x = k + 2; x <= n; ++x) {
        a.push_back(x);
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;

    vector<int> ans = constructPermutation(n, k);

    // 输出
    for (int i = 0; i < (int)ans.size(); ++i) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

题目内容

小红希望你构造一个长度为 $n$ 的排列，其中恰好有 $k$ 对相邻的数满足前一个数人大于后一个数，可以证明，对于任意 $k>n$ ，都存在一个合法的排列。你能帮帮她吗？

【名词解释】

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

输入描述

在一行上输入两个整数 $n,k(1≤k＜n≤10^5)$ 。

输出描述

在一行上输出 $n$ 个整数，表示你所构造的一个合法排列。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确，注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

5 2

输出

1 4 2 5 3

样例2

输入

3 2

输出

3 2 1