O(n)的解法：动态规划
这样考虑，1到m中，第s个元素距离第1个元素的位置是((s-1) % m) +1。设开始的时候猴子的位置为f(m,n)，当第n个离开后，还剩下m-1个猴子，并且要从第( (n -1)% m) + 1的位置继续数下n个猴子。剩下的圈里的猴子的位置这时就变成了f(m-1,n)，于是有如下的递归式:
f(i,n) = ( f(i-1,n) + k - 1) % i + 1, f(1,n) = 1, i = 2~m
#include
#include
#include
using namespace std;
int main()
{
int m,n;
cout<<"Input m and n: "< cin>>m>>n;
if(m cout<<"Error! m is less than n"< else
{
int king = 1;
for(int i=2; i<=m; i++)
{
king = (king + n - 1) % i + 1;
}
cout<<"King is: "< }
return 0;
}
