自动搬运

查看原文

来自洛谷，原作者为

	mcturtle 求求了给个关注吧，壶关请在犇犇@，目前不互棕封灰蓝绿橙，橙及以上有勾或活跃必互||新一年级（小朋友多多关照）铁迷/飞友/MC and Bed Wars er(Easecation 97级)/现役OIer/……（成分复杂||ENTP喵

搬运于2025-08-24 21:17:33，当前版本为作者最后更新于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)}$，可以通过所有数据。