ZHK

ZHK

一只叫ZHK的蒟蒻为了RP而战

题解 P2755 【洗牌问题】

posted on 2019-01-26 11:38:39 | under 题解 |

这是本人的第一篇题解

请多多宽恕

这一道题其实不要用数组

我们来观察一下n=3时的情况:

原: 1 2 3 4 5 6

4 1 5 2 6 3

2 4 6 1 3 5

1 2 3 4 5 6

我们去观察2的位置

第一次的位置:2

第二次的位置:4

第三次的位置:1

因为2是前半堆牌,所以可以直接乘2,所以我们发现4是2的倍数

因为4是后半堆牌,所以是要先找到它对应的前面的牌——4-3,然后找到它的位置,(4-3)2,然后后面的牌是在它对应的前面牌的位置-1,所以,是(4-3)2-1,我们算一下,发现是1,确实是正确答案,所以,我的方法是对的

我们来用程序实现

用i来模拟,就得出了这样一个公式

if(i>n)i=(i-n)*2-1;//如果它在后半堆,找到它对应的前面的牌,算出它对应的前面的牌的位置,再-1
else i=i*2;//如果它在前半堆,直接乘以2

那么AC代码是


#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,i=1,s=0;//只要第1张牌回到了初始位,整付牌就回到了初始状态
    cin>>n;//读入
    do{
        if(i>n)i=(i-n)*2-1;//如果它在后半堆,找到它对应的前面的牌,算出它对应的前面的牌的位置,再-1
        else i=i*2;//如果它在前半堆,直接乘以2
        s++;
    }while(i!=1);
    cout<<s;
    return 0;
}```