自动搬运

查看原文

来自洛谷，原作者为

	yummy 这个人是时代的眼泪，什么也没有留下

搬运于2025-08-24 21:33:02，当前版本为作者最后更新于2018-08-23 01:09:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到各位大佬们使用各种方法，数学优化，二分等，本蒟蒻很感(wu)慨(yu)，因为我不会呀，，然而，经过我的思考，本题完全没有必要死磕，可以使用一种巧妙的方法。

Updated at Aug.28:修改使其更规范，把不容易理解的部分讲的更详细一些。

首先，在做此题之前，我们需要了解到的一点是：不管一张牌上面写的数字是几，只要牌的总量不变，牌的位置不变，最终这张牌到达的位置总是不变的。

换言之，一个班级（牌堆）定期换座位（洗牌），如果换座位的规则（操作牌的顺序）一直不变，那么不管某张桌子上坐着谁，这个同学换完座位后到达的位置只和桌子位置有关。

对于本题，我们需要求的一个关键数组是每个位置的同学（牌）换座位（洗牌）之后被换到了哪个位置。为了解决这个问题，我们可以假设这个牌叠是 $1,2,3,...,n$，然后按题意用STL库里的queue模拟一遍，以 $n=10$ 举个栗子。

通过模拟，我们发现，原数列变成了 $2,4,6,8,10,3,7,1,9,5$。

这里，$a_1=2$ 不仅表示按顺序排的牌堆中 $1$ 变到了 $2$ 的位置，还意味着所有在 $1$ 位置的牌都会被移动到 $2$ 位置。

于是，更关键的操作：如果想要让 $2$ 位置出现 $2$，我们需要让原来的 $1$ 位置的牌变成 $2$。

(下行是我们要的答案）

那么，根据这种方法，就可以求解了，复杂度 $O(n)$

为满足一些人的情绪，贴代码——

#include<iostream>
#include<cstdio>
#include<queue>//头文件，不用解释
using namespace std;
queue<int>a;
int sc[1000005],ans[1000005];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        a.push(i);//先制造一叠牌(1,2,...,n)
    for(int i=1;!a.empty();i++)//开始模拟
    {
        a.push(a.front());
        a.pop();
        sc[i]=a.front();
        a.pop();
    }
    for(int i=1;i<=n;i++)//将i放在sc[i]处，经过一通操作后，就在正确的位置了
        ans[sc[i]]=i;
    for(int i=1;i<=n;i++)//输出
        cout<<ans[i]<<" ";
    return 0;
}