| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:终于不打表AC,282ms,放出代码,求更快的解法……In Reply To:终于不打表AC,282ms,放出代码,求更快的解法…… Posted by:alexneko at 2008-07-12 16:14:45 跟你的思路差不多,但是我的执行时间要长一倍,可能是因为G++和STL的缘故、
#include <iostream>
#include <vector>
using namespace std;
int joseph[14];
int Joseph(int k) {
int m;
int NumOfGuys = 2 * k;
//the kicking-out process
int starter;
int i;//index of the kicked out person
int n = NumOfGuys;//number of persons in the circle
m = k + 1;
while (n > k) {
n = NumOfGuys;
starter = 0;
while (n > k) {
i = (starter + m - 1) % n;
//a good guy is kicked out
if (i < k) {
m ++;
break;
}
n --;
starter = i;
}
}
return m;
}
int main() {
int k;
vector<int> results;
vector<int>::iterator it;
//pre-store the results
for (int i = 1; i < 14; i ++) {
joseph[i] = Joseph(i);
}
//for (cin >> k; k != 0; N ++) {
cin >> k;
while (k != 0) {
results.push_back(joseph[k]);
cin >> k;
}
for (it=results.begin() ; it < results.end(); it++) {
cout << *it << endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator