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

· · 题解

前言

做为一个bcsp6月小高组差0.5分的小蒟蒻，所以为了弥补一下心中的意难平，我打算写这篇题解弥补一下。

题意

让你模拟选择排序的过程并打印。

思路

不能直接模拟，因为极限数据n是10的5次方，而选择排序的最坏时间复杂度是n的平方，很显然不行。

那怎么办呢？可以进行优化

我们要快速找到 第i 小的元素，我们确定最大值不超过n，且每个数只会出现一次。

我们用一个标记数组， cnt[i]标记 i出现的下标。一定注意下标为 i和元素值为 i 的下标交换的时候，要将他们相对应的标记数组进行交换。时间复杂度为 O(nm) 。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],cnt[N];//创建标记数组
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        cnt[a[i]]=i;//标记
    }
    int rp=1;//设好初始值
    while(m--){
        int x;
        cin>>x;
        //模拟选择排序
        for(int i=rp;i<=x;i++){
            int t1=cnt[i],t2=a[i];
            //因为cnt[i]和cnt[a[i]]会在后面进行swap，为了方便后面的cnt数组的交换所以提前交换
            swap(a[i],a[cnt[i]]);
            cnt[i]=i;
            cnt[t2]=t1;
        }
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" ";
        }
        rp=x;//更新变量要记得
        cout<<endl;
    }
    return 0;//养成好习惯
}

本蒟蒻的第一篇题解，希望能过qwq