n只猴子要选大王，选举方法如下：所

有猴子按 1，2 ……… n 编号并按照顺序围成一圈，

从第 k 个猴子起，由1开始报数，报到m时，该猴子就跳出圈外，

下一只猴子再次由1开始报数，

如此循环，直到圈内剩下一只猴子时，这只猴子就是大王。

 

#include
     
      #include
      
       using namespace std;int main(){    int m,n;    cin>>m>>n;    vector
       
         v;    for(int i=1; i<=m; i++)    {        v.push_back(i);    }    int t=1;    while(m>1)    {            t+=n-1;        t=!(t%m)?m:t%m;        v.erase(v.begin()+t-1);    //删除当前vector中第t个元素        m--;    }    cout<
        
         <
        
       
      
     

 

 

 下面这种大同小异，只不过更容易理解

#include
     
      #include
      
       using namespace std;int main(){    int m,n;    cin>>m>>n;    vector
       
         v;    for(int i=1; i<=m; i++)    {        v.push_back(i);    }    int t=1;    while(v.size()>1)    {            t+=n-1;        t=!(t%v.size())?v.size():t%v.size();        v.erase(v.begin()+t-1);    //删除当前vector中第t个元素    }    cout<
        
         <
        
       
      
     

 

下面是用C语言写的，没有任何技巧性

#include
     
      #define Maxsize 100double max_min(int i, int* a){    int m, n, r;    int *p, *q;    double s = 0, min, max, maxmin;    for (m = 2; m <= i; m++)  //子列长度    {        p = a;    //子列首元素指针        q = a;        for (n = 1; n <= i - m + 1; n++)   //子列起始位置        {                        for (r = 1; r < m; r++)                 {                q++;                max = (double)*p;                min = (double)*p;                if (max<*q)                    max = *q;                if (min>*q)                    min = *q;                            }                p++;            q = p;            maxmin = max - min;             s += maxmin;        }    }    return s;}int main(){    int i, j;    double s;    int a[Maxsize];    scanf("%d", &i);    for (j = 0; j
     

 

其实题目的思想很简单，但是花了两个多小时才完成！！！

突破口1：一点点数学技巧

突破口2：使用vector容器

 

第一次看到题目后就想到了list，折腾了一个多小时还是不行，不得不转变思路。。

于是用了和数组最相近的vector容器，还真就成功了，哈哈！！

 

 

 

##############################这是分界线，是不一样的我##########################################

 

 

2016.4.21

上面的几个代码都是模拟法，复杂度为log(nm)面对大数据就心有余而力不足了……

今天在上面看到约瑟夫问题，可以进行bp优化的~优化后为log(n)，爽

//约瑟夫问题dp优化 #include
     
      using namespace std;int k;int fun(int n){    if(n == 1)        return 0;    else if(n <= k)        return (fun(n - 1) + k) % n;    else{        if(fun(n - n / k) < n % k)            return n - n % k + fun(n - n / k);         else            return fun(n - n / k) - n % k + (fun(n - n / k) - n % k) / (k - 1);    }}int main(){    int T, N;    cin >> T;    while(T--){        cin >> N >> k;        cout << fun(N) << endl;    }        return 0;}