hdu4841---圆桌问题解题报告(约瑟夫环问题---数组,queue,vector三种实现方式)
圆桌问题链接
输入:n(好人数,坏人数),m(数到m杀人,接着从1开始数)
输出:G为好人,B为坏人,坏人全部会在被杀的位置。
三种实现方式:
1.最朴素的数组:(模拟整个过程)
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<list>
#define mod 998244353
#define INF 0x3f3f3f3f
#define Min 0xc0c0c0c0
#define mst(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i = a; i < b; i++)
using namespace std;
typedef long long ll;
const int MAX_N = 32767;
bool vis[2 * MAX_N];
int main(){
//freopen("c1.txt", "w", stdin);
//freopen("c2.txt", "r", stdout);
//ios::sync_with_stdio(false);
int n, m;
while(scanf("%d%d", &n, &m) != EOF){
for(int i = 1; i <= 2 * n; i++){
vis[i] = true;
}
int sum = 2 * n;
int cur = 0;
while(sum > n){
for(int i = 1; i <= 2 * n; i++){
if(!vis[i]){
continue;
}
if(sum <= n){ //这里的判断尤其重要,不然杀人数可能会超过n
break;
}
cur++;
if(cur == m){
vis[i] = false;
cur = 0;
sum--;
}
}
}
for(int i = 1; i <= 2 * n; i++){
if(!vis[i]){
printf("B");
}
else {
printf("G");
}
if(i % 50 == 0) printf("\n");
}
printf("\n\n");
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
2.队列实现,明显方便很多,什么预判都不用想,直接写。
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<list>
#define mod 998244353
#define INF 0x3f3f3f3f
#define Min 0xc0c0c0c0
#define mst(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i = a; i < b; i++)
using namespace std;
typedef long long ll;
const int MAX_N = 32767;
bool vis[2 * MAX_N];
int main(){
//freopen("c1.txt", "w", stdin);
//freopen("c2.txt", "r", stdout);
//ios::sync_with_stdio(false);
int n, m;
while(~scanf("%d%d", &n, &m)){
queue<int> q;
for(int i = 1; i <= 2 * n; i++){
q.push(i);
vis[i] = false;
}
int cur = 0;
while(q.size() > n){
cur++;
int x = q.front();
if(cur == m){
cur = 0;
q.pop();
vis[x] = true;
}
else {
q.pop();
q.push(x);
}
}
for(int i = 1; i <= 2 * n; i++){
if(vis[i]){
printf("B");
}
else {
printf("G");
}
if(i % 50 == 0){
printf("\n");
}
}
printf("\n\n");
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
3.vector(出于学习的角度写的),vector的i必须从0开始,由于不熟练,写的过程WA了好几次
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<list>
#define mod 998244353
#define INF 0x3f3f3f3f
#define Min 0xc0c0c0c0
#define mst(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i = a; i < b; i++)
using namespace std;
typedef long long ll;
const int MAX_N = 32767;
bool vis[2 * MAX_N];
int main(){
//freopen("c1.txt", "w", stdin);
//freopen("c2.txt", "r", stdout);
//ios::sync_with_stdio(false);
int n, m;
while(~scanf("%d%d", &n, &m)){
mst(vis);
vector<int> v(2 * n);
for(int i = 0; i < 2 * n; i++){ //vector数组只能从0开始填充
v[i] = i;
}
int cur = 0;
while(v.size() > n){
cur = (cur + m - 1) % v.size(); //vector数组中被杀那个人的位置
vis[v[cur]] = 1; //记录这个人开始的位置
v.erase(v.begin() + cur); //清除该位置的人
}
for(int i = 0; i < 2 * n; i++){
if(vis[i]){
printf("B");
}
else {
printf("G");
}
if( (i + 1) % 50 == 0){
printf("\n");
}
}
printf("\n\n");
}
//fclose(stdin);
//fclose(stdout);
return 0;
}