1、常规解法，用list 容器：
#include<iostream> #include<list> using namespace std; int lastremaining(list<int> q, int m) { int len = q.size(); list<int>::iterator current = q.begin(); while (q.size()>1) { for (int i = 1; i<m; i++) { current++; if (current == q.end()) current = q.begin(); } cout << *current << endl; list<int>::iterator next = q.erase(current); //若这行写成这样q.erase(current)，删除元素后，容器指针current指向的不是下一个元素，而是成为了野指针，所以程序会报错 if (next == q.end())next = q.begin(); //且当删除最后一个元素时，此时容器指针current指向末尾的下一个位置，此时也就成为野指针，所以会报错。所以这里要判断一下 current = next; //cout << *current << endl; } return *current; } int main() { int n; cin >> n; if (n>1000)return -1; list<int>qlist; for (int i = 0; i<n; i++) qlist.push_back(i); int res = 0; res = lastremaining(qlist, 3); cout << res << endl; system("pause"); return res; }
2、公式法
递归公式：
f[1] = 0 f[n] = (f[n - 1] + K) mod n
1.当只有1个候选人时，最后一个剩下来的编号为0，毫无疑问的。
2.当有n-1个候选人时，则假设已经算出它最后的一个剩余的编号为s，即f[n]=s则有n个候选人是剩余的编号则为f[n] = (f[n - 1] + K) mod n
一个例子：
假设我们已经求解出了f[n - 1]，并且保证f[n - 1]的值是正确的。 现在先将n个人按照编号进行排序： 0 1 2 3 … n-1 那么第一次被淘汰的人编号一定是K-1(假设K < n，若K > n则为(K-1) mod n)。将被选中的人标记为”#”： 0 1 2 3 … K-2 # K K+1 K+2 … n-1 第二轮报数时，起点为K这个候选人。并且只剩下n-1个选手。假如此时把k看作0’，k+1看作1’… 则对应有：
0 1 2 3 ... K-2 # K K+1 K+2 ... n-1 n-K' n-2' 0' 1' 2' ... n-K-1' 12 12此时在0’,1’,…,n-2’上再进行一次K报数的选择。而f[n-1]的值已经求得，因此我们可以直接求得当选者的编号s’。 但是，该编号s’是在n-1个候选人报数时的编号，并不等于n个人时的编号，所以我们还需要将s’转换为对应的s。 通过观察，s和s’编号相对偏移了K，又因为是在环中，因此得到s = (s'+K) mod n。 即f[n] = (f[n-1] + k) mod n。
上述过程的时间复杂度为O(N),空间复杂度为O(1)
#include <iostream> using namespace std; int lastNum(int n,int k) { if (n==1) return 0; if (n<k) { int res=0; for (int i=2;i<=n;i++) res=(res+k)%i; return res; } } int main(){ int num;cin>>num;
int n,k; while (num--)
{ cin>>n>>k;
cout<<lastNum(n,k)<<endl;
}
return 0;
}
