新第k人-白红宇

新第k人

阅读量：2038 次

发布时间：2019-04-28

本文共 1278 字，大约阅读时间需要 4 分钟。

题解：经典的约瑟夫环问题

参考

如果不一次处理完，重复操作可能超时

C++版本一

/**@Author:   STZG*@Language: C++*/#include 
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   //#define DEBUGusing namespace std;typedef long long ll;const int N=10000+10;const double PI = acos(-1.0);const double EXP = 1E-8;const int INF = 0x3f3f3f3f;int t,n,m;int a[N];int yuesefu(int n,int m){ if(n == 1){ return 0; //这里返回下标,从0开始，只有一个元素就是剩余的元素0 } else{ a[n-1]=yuesefu(n-1,m); return (a[n-1] + m) % n; //我们传入的n是总共多少个数 }}int main(){#ifdef DEBUG freopen("input.in", "r", stdin); //freopen("output.out", "w", stdout);#endif scanf("%d",&t); a[10000]=yuesefu(10000,233); while(t--){ scanf("%d",&n); cout<
                   
                    <

C++版本二

题解：

因为一直k 是233，所有人站成一个环，如果知道了x 个站成一个环的时候，出去人的相对顺序（最后一个出去的人的序列是1，第一个出去的人的编号是x），那么可以通过这个顺序知道x+1 个人占成一个环的时候，出去的相对顺序。即找到编号为x 的人，往前数232 个人和第233 个人之间插入一个位置，这个位置就是编号为x+1 的人。

#include
   
    using namespace std;const int N = 1e5 + 10;int f[N];int main(){    f[1] = 0;    for(int i = 2; i < N; ++i)  f[i] = (f[i - 1] + 233) % i;    int t;    scanf("%d", &t);    while(t--){        int n;        scanf("%d", &n);        printf("%d\n", f[n] + 1);    }    return 0;}

转载地址：http://myzof.baihongyu.com/

你可能感兴趣的文章