题解 P2021 【faebdc玩扑克】

· · 题解

看到各位大佬们使用各种方法，数学优化，二分等，本蒟蒻很感(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;
}