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

# B4171 [BCSP-X 2024 6 月小学高年级组] 选择排序 题解
**免责声明**：此题解是对 [mcturtle的题解](https://www.luogu.com.cn/article/9wo19mxj)的分析
### 1. 读题
- 模拟选择排序的过程。
- 时间复杂度不能为 $\operatorname{O (n^2)}$。
- **重点：保证 $A$ 是排列，即 $1～n$ 每个数恰好出现一次**
---
### 2. 解题思路
- 由于直接模拟选择排序会导致超时所以我们需要一种新思路[这是错误示例](https://www.luogu.com.cn/record/205567464)。
- 用数组 $t$ 标记每一个需要交换的值，如 `t[a[i]]=i` 也可以理解为相对于 $a$ 数组,数组与下标反着使用。
- 每次交换 $a$ 数组 $t$ 数组都需要换。
---
### 3. 代码片段分析
- 数据的定义、准备与输入：
```
 #include<bits/stdc++.h>
 using namespace std;
 const int N=1e6+10;
 int n,m,a[N],m1,t[N];
//n :被排序数字的个数。
//m :查询次数。
//m1 :当前查询。
//t :标记数组。
 int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        t[a[i]]=i;//边输入边标记。
    }
```
- 选择排序模拟部分与输出：
```
    int m2=1;//从上一次的查询位置开始遍历。
    while(m--)// m 次查询。
    {
        int m1;
        cin>>m1;//边读入边计算
        for(int i=m2;i<=m1;i++){//从上一次的查询位置开始遍历。
            int t1=t[i],t2=a[i];//由于 a[i]、 t[i] 的值会不断变化，需要先记录。
            swap(a[i], a[t[i]]);
            t[i]=i;
            t[t2]=t1;
        }
        for (int i=1;i<=n;i++)
            cout<<a[i]<<" ";
        m2=m1;//查询位置需要更新。
		cout<<endl;//千万别忘了换行。
    }
```
---
### 4. AC代码
由于此题解是对 [mcturtle 的题解](https://www.luogu.com.cn/article/9wo19mxj)的分析，就不出示 AC 代码了。

此蒟蒻的第一篇题解，有问题请指出，不喜轻喷！（求过）

正在渲染内容...

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

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