题解：B4171 [BCSP-X 2024 6 月小学高年级组] 选择排序

_Ec__yt_qwq_ · 2025-02-20 18:30:00 · 题解

题意

其实很简洁，让你模拟选择排序的过程。

思路

我们要通过此题，肯定不能直接模拟，因为 n\le10^5，而选择排序的最坏时间复杂度为 \mathtt{O(n^2)}，很显然是不行的。

考虑进行优化。

我们需要快速的找到第 i 小的元素。我们可以确定该数组的最大值在 n 之内，同时每个数只会出现一次。

我们使用一个标记数组，t_i 表示 i 出现的下标。然后要注意每次交换，下标为 i 和元素值为 i 的下标交换的时候，需要将他们相对应的标记数组也进行交换。

#include <bits/stdc++.h>
using namespace std;
int a[100005], t[100005];//要使用标记数组
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        t[a[i]] = i;//打标记
    }
    int c = 1;//初始值设好
    while (m--)
    {
        int x;
        cin >> x;
        for (int i = c; i <= x; i++)//从上一次的x开始遍历
        {
            int t1 = t[i], t2 = a[i];//准备工作
            swap(a[i], a[t[i]]);//STL交换
            t[i] = i;//temp变量交换
            t[t2] = t1;//t[a[i]] = t[i]
        }
        for (int i = 1; i <= n; i++)
        {//输出
            cout << a[i] << " ";
        }
        c = x, cout << endl;//更新变量，换行别忘记
    }
}

复杂度 \mathtt{O(nm)}，可以通过所有数据。