解题思路

核心算法

使用贪心策略结合位置映射表，从左到右逐个位置确保放置最优值。

关键观察

1. 字典序最小的本质：要使字典序最小，应该让前面的位置尽可能放置小的数字
2. 最优排列的特征：理想情况下，位置i（0-indexed）应该放置值i+1
3. 贪心策略的正确性：优先处理前面的位置，因为前面位置对字典序的影响更大

算法设计思路

贪心策略

从左到右遍历每个位置，对于位置i：

• 如果当前位置a[i]已经等于理想值i+1，无需操作
• 如果a[i] ≠ i+1，需要找到值为i+1的元素并交换到位置i
• 每次交换消耗一次操作机会

高效查找机制

为了避免每次都线性搜索目标值的位置，采用位置映射表：

• 预处理阶段：建立pos[value] = index的映射关系
• 查找阶段：通过pos[target]直接获取目标位置
• 维护阶段：每次交换后同步更新映射表

具体执行步骤

1. 初始化：创建位置映射表pos，使得pos[a[i]] = i
2. 贪心处理：从位置0开始逐个处理
   • 对于位置i，理想值为target = i+1
   • 如果a[i] ≠ target且还有交换次数，执行交换
   • 找到target所在位置j = pos[target]
   • 更新映射表：pos[a[i]] = j, pos[target] = i
   • 交换a[i]和a[j]，交换次数减1
3. 终止条件：交换次数用完或已达到最优状态

代码实现

Python

def solve():
    # 读取输入
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    
    # 建立值到位置的映射
    pos = [0] * (n + 1)  # pos[value] = index
    for i in range(n):
        pos[a[i]] = i
    
    # 贪心策略：从左到右为每个位置放置最优值
    for i in range(n):
        # 如果交换次数用完，直接退出
        if m == 0:
            break
        
        # 如果当前位置不是最优值（应该是i+1）
        target = i + 1
        if a[i] != target:
            # 通过映射表直接找到目标值的位置
            j = pos[target]
            
            # 交换前先更新位置映射
            pos[a[i]] = j
            pos[a[j]] = i
            
            # 交换当前位置和目标位置
            a[i], a[j] = a[j], a[i]
            m -= 1  # 消耗一次交换机会
    
    # 输出结果
    print(' '.join(map(str, a)))

# 处理多组测试数据
T = int(input())
for _ in range(T):
    solve()

Java

import java.util.*;

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();
            int m = sc.nextInt();
            int[] a = new int[n];
            
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            
            // 建立值到位置的映射
            int[] pos = new int[n + 1]; // pos[value] = index
            for (int i = 0; i < n; i++) {
                pos[a[i]] = i;
            }
            
            // 贪心策略：从左到右为每个位置放置最优值
            for (int i = 0; i < n && m > 0; i++) {
                // 如果当前位置不是最优值（应该是i+1）
                int target = i + 1;
                if (a[i] != target) {
                    // 通过映射表直接找到目标值的位置
                    int j = pos[target];
                    
                    // 交换前先更新位置映射
                    pos[a[i]] = j;
                    pos[target] = i;
                    
                    // 交换当前位置和目标位置
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    
                    m--; // 消耗一次交换机会
                }
            }
            
            // 输出结果
            for (int i = 0; i < n; i++) {
                System.out.print(a[i]);
                if (i < n - 1) System.out.print(" ");
            }
            System.out.println();
        }
        
        sc.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T;
    
    // 处理多组测试数据
    while (T--) {
        // 读取输入
        int n, m;
        cin >> n >> m;
        
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        // 建立值到位置的映射
        vector<int> pos(n + 1); // pos[value] = index
        for (int i = 0; i < n; i++) {
            pos[a[i]] = i;
        }
        
        // 贪心策略：从左到右为每个位置放置最优值
        for (int i = 0; i < n && m > 0; i++) {
            // 如果当前位置不是最优值（应该是i+1）
            int target = i + 1;
            if (a[i] != target) {
                // 通过映射表直接找到目标值的位置
                int j = pos[target];
                
                // 交换前先更新位置映射
                pos[a[i]] = j;
                pos[target] = i;
                
                // 交换当前位置和目标位置
                swap(a[i], a[j]);
                
                m--; // 消耗一次交换机会
            }
        }
        
        // 输出结果
        for (int i = 0; i < n; i++) {
            cout << a[i];
            if (i < n - 1) cout << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

题目内容

给定一个长度为 $n$ 的排列 {$a_1,a_2,...,a_n$} 。

你可以进行至多 m 次以下操作：

• 选择两个索引 $i,j$，交换 $a_i$ 与 $a_j$ 。

请输出在经过至多 $m$ 次交换操作后能够得到的字典序最小的排列。

【名词解释】

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

字典顺序比较：从数组的第一个元素开始逐个比较，直到找到第一个不同的位置，通过比较这个位置元素的大小得出数组的大小，称为字典顺序比较。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 $T(1 ≤ T ≤ 10^4)$ ，代表数据组数；

随后对于每组数据，按以下格式输入：

• 第一行输入两个整数

$n,m(1≦n≦2×10^5,1≦m≤10^9)$，分别表示排列长度和允许的交换次数；

• 第二行输入一个长度为 n 的排列

{ $a_1,a_2,...,a_n$ } $(1≤a_i≤n)$ 。

保证所有测试数据中 $n$ 的总和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，在一行上输出一个长度为 $n$ 的排列，表示经过至多 $m$ 次交换操作后得到的字典序最小的排列。

样例1

输入

2
2 1
2 1
3 4
3 2 1

输出

1 2
1 2 3

说明

在第二个测试用例中，可以选择交换 $(i,j)=(1,3)$ ，将排列 { $3,2,1$ }变为{ $1,2,3$ }。