构造思路

考虑如何精确制造出 $m$ 个谷值。

关键观察：如果我们让前一段序列严格递增，则从第 3 个位置开始，每个新元素都会形成一个谷值。 例如：

• 长度为 $k$ 的递增段可以制造出 $k-2$ 个谷值。

因此，只要在前面构造一个长度为 $m+2$ 的严格递增段，就能制造出正好 $m$ 个谷值。 接下来的数必须避免继续产生谷值，可以把剩余的数按严格递减顺序排列即可，因为这样不会超过前两个较大的数。

具体构造方法

1. 取最大的 $m+2$ 个数（即 $[\,n-m-1, n-m+2, \dots, n\,]$），按升序放在前 $m+2$ 个位置。 这样保证了连续 $m$ 个谷值。
2. 将剩下的数 $[1,2,\dots,n-m-2]$ 按降序放在剩余的位置。 这样保证后续不会再出现新的谷值。

示例

输入：$n=5,m=2$

• 前 $m+2=4$ 位放最大 4 个数：2,3,4,5。
• 剩余数 1 递减放在最后。 结果：[2,3,4,5,1]。 检查：
• $i=3$: 4 > max(2,3) → 是谷值
• $i=4$: 5 > max(3,4) → 是谷值
• $i=5$: 1 > max(4,5) → 否 恰好 2 个谷值。

复杂度分析

• 每组数据只需一次构造和输出，时间复杂度 $O(n)$。
• 空间复杂度 $O(1)$（除输出存储外）。

适合 $T$ 组数据，且总 $\sum n \le 2\times 10^5$。

参考实现

Python

import sys

def solve():
    data = sys.stdin.read().strip().split()
    t = int(data[0])
    idx = 1
    out = []
    for _ in range(t):
        n = int(data[idx]); m = int(data[idx+1]); idx += 2
        ans = []
        # 前 m+2 个位置放 [n-m-1 .. n]
        for x in range(n - m - 1, n + 1):
            ans.append(x)
        # 剩余放 [n-m-2 .. 1] 递减
        for x in range(n - m - 2, 0, -1):
            ans.append(x)
        out.append(" ".join(map(str, ans)))
    print("\n".join(out))

if __name__ == "__main__":
    solve()

Java 实现

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine().trim());
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            // 前 m+2 个位置
            for (int x = n - m - 1; x <= n; ++x) {
                sb.append(x).append(' ');
            }
            // 剩余部分递减
            for (int x = n - m - 2; x >= 1; --x) {
                sb.append(x);
                if (x > 1) sb.append(' ');
            }
            sb.append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++ 实现

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

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

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<int> ans;
        ans.reserve(n);
        // 前 m+2 位放大数递增
        for (int x = n - m - 1; x <= n; ++x) ans.push_back(x);
        // 剩余部分递减
        for (int x = n - m - 2; x >= 1; --x) ans.push_back(x);
        for (int i = 0; i < n; ++i) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

题目内容

给定两个整数 $n,m$，请输出一个长度为 $n$ 的排列 $a_1,a_2,…,a_n$，使得排列中 “谷值"的个数 恰好为 $m$ 。定义：当 $3≤i≤n$ 时，如果 $max(a_{i−2},a_{i−1})≤a_i$ ，则认为位置 $i$ 形成一个"谷值”。

输入描述

第一行一个整数 $T (1≤T≤10^5)$，表示测试数据组数。

接下来每行两个整数 $n,m(3≤n≤2×10^5, 0≤m≤n−2)$ 。

每组的$n$之和不超过$2×10^5$

输出描述

对于每组数据，输出一个长度为 $n$ 的排列。若有多个解，输出任意一个。

样例1

输入

2
3 0
5 2

输出

1 2 3
3 4 5 2 1