笔试时间：2025年8月10日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：排列最小化

给定一个长度为  n  的排列  {a₁, a₂, …, aₙ} 。 你可以进行至多  m  次以下操作：选择两个索引  i, j ，交换  aᵢ  与  aⱼ 。请输出在经过至多  m  次交换操作后能够得到的字典序最小的排列。

【名词解释】排列：长度为  n  的排列是由  1 ~ n  这  n  个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如， {2, 3, 1, 5, 4}  是一个长度为  5  的排列，而  {1, 2, 2}  和  {1, 3, 4}  都不是排列，因为前者存在重复元素，后者包含了超出范围的数。字典顺序比较：从数组的第一个元素开始逐个比较，直到找到第一个不同的位置，通过比较这个位置元素的大小得出数组的大小，称为字典顺序比较。

输入描述

每个测试文件均包含多组测试数据。 第一行输入一个整数  T (1 ≦ T ≦ 10⁴) ，代表数据组数； 随后对于每组数据，按以下格式输入：第一行输入两个整数  n, m (1 ≦ n ≦ 2×10⁵, 1 ≦ m ≦ 10⁹) ，分别表示排列长度和允许的交换次数；第二行输入一个长度为  n  的排列  {a₁, a₂, …, aₙ} (1 ≦ aᵢ ≦ n) 。保证所有测试数据中  n  的总和不超过  2×10⁵ 。

输出描述

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

样例输入

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} 。

参考题解

我们要得到字典序最小的排列。 字典序的贪心原则是：从前往后扫描，每个位置尽可能放最小的可用数。如果当前位置不是最小的数，就把它和这个最小数所在的位置交换。每次交换次数 m 减 1，直到用完或者数组遍历结束。我们知道排列是 1 ~ n 的全排列，所以位置 i 应该放最小的、还没放好的数字。 用一个数组 pos[val] 记录数字 val 的位置，这样可以 O(1) 定位交换位置。

C++：

#include <iostream>
#include <vector>
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> a(n);
        vector<int> pos(n + 1);  // 存储每个值的位置
        
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            pos[a[i]] = i;
        }
        
        int cur_min = 1;
        for (int i = 0; i < n; ++i) {
            if (m == 0) break;
            
            if (a[i] != cur_min) {
                // 交换a[i]与cur_min所在位置的元素
                int j = pos[cur_min];
                swap(a[i], a[j]);
                
                // 更新位置映射
                pos[a[j]] = j;
                pos[a[i]] = i;
                
                m--;
            }
            cur_min++;
        }
        
        // 输出结果
        for (int i = 0; i < n; ++i) {
            if (i > 0) cout << " ";
            cout << a[i];
        }
        cout << "\n";
    }
    
    return 0;
}

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));
        PrintWriter pw = new PrintWriter(System.out);
        
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            
            int[] a = new int[n];
            int[] pos = new int[n + 1];  // 存储每个值的位置
            
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; ++i) {
                a[i] = Integer.parseInt(st.nextToken());
                pos[a[i]] = i;
            }
            
            int curMin = 1;
            for (int i = 0; i < n; ++i) {
                if (m == 0) break;
                
                if (a[i] != curMin) {
                    // 交换a[i]与curMin所在位置的元素
                    int j = pos[curMin];
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    
                    // 更新位置映射
                    pos[a[j]] = j;
                    pos[a[i]] = i;
                    
                    m--;
                }
                curMin++;
            }
            
            // 输出结果
            for (int i = 0; i < n; ++i) {
                if (i > 0) pw.print(" ");
                pw.print(a[i]);
            }
            pw.println();
        }
        
        pw.close();
    }
}

Python：

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    pos = [0] * (n + 1)
    for idx, val in enumerate(a):
        pos[val] = idx

    cur_min = 1
    for i in range(n):
        if m == 0:
            break
        if a[i]