HDU4841 圆桌问题【约瑟夫环+模拟+STL】

Daphne ·

更新时间:2024-09-21

· 558 次阅读

圆桌问题

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 6757 Accepted Submission(s): 2550

Problem Description
圆桌上围坐着2n个人。其中n个人是好人，另外n个人是坏人。如果从第一个人开始数数，数到第m个人，则立即处死该人；然后从被处死的人之后开始数数，再将数到的第m个人处死……依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位，能使得在处死n个人之后，圆桌上围坐的剩余的n个人全是好人。

Input
多组数据，每组数据输入：好人和坏人的人数n（<=32767）、步长m（<=32767）；

Output
对于每一组数据，输出2n个大写字母，‘G’表示好人，‘B’表示坏人，50个字母为一行，不允许出现空白字符。相邻数据间留有一空行。

Sample Input
2 3
2 4

Sample Output
GBBG

BGGB

问题链接：HDU4841 圆桌问题
问题简述：（略）
问题分析：
约瑟夫环问题，用模拟法来解决。
可以用数组实现模拟，也可以用STL的向量vector实现模拟，也可以用STL的队列queue实现模拟。也许使用STL的链表list也可以实现模拟。
程序说明：（略）
参考链接：（略）
题记：（略）

AC的C++语言程序（数组模拟）如下：

/* HDU4841 圆桌问题 */
#include 
using namespace std;
const int N = 32767;
const int N2 = 2 * N;
bool flag[N2];
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m)) {
        memset(flag, true, sizeof(flag));
        int sum = 2 * n, cur = 0;
        while(sum > n) {
            for(int i = 0; i < 2 * n; i++) {
                if(!flag[i]) continue;
                if(sum <= n) break;
                cur++;
                if(cur == m) {
                    flag[i] = false;
                    cur = 0;
                    sum--;
                }
            }
        }
        for(int i = 0; i < 2 * n; i++) {
            putchar(flag[i] ? 'G' : 'B');
            if((i + 1) % 50 == 0) putchar('\n');
        }
        putchar('\n');
        putchar('\n');
    }
    return 0;
}

AC的C++语言程序（使用vector模拟）如下：

/* HDU4841 圆桌问题 */
#include 
using namespace std;
const int N = 32767;
const int N2 = 2 * N;
bool flag[N2];
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m)) {
        memset(flag, true, sizeof(flag));
        vector v(2 * n);
        for(int i = 0; i  n) {
            cur = (cur + m -1) % v.size();
            flag[v[cur]] = false;
            v.erase(v.begin() + cur);
        }
        for(int i = 0; i < 2 * n; i++) {
            putchar(flag[i] ? 'G' : 'B');
            if((i + 1) % 50 == 0) putchar('\n');
        }
        putchar('\n');
        putchar('\n');
    }
    return 0;
}

AC的C++语言程序（使用queue模拟）如下：

/* HDU4841 圆桌问题 */
#include 
using namespace std;
const int N = 32767;
const int N2 = 2 * N;
bool flag[N2];
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m)) {
        memset(flag, true, sizeof(flag));
        queue q;
        for(int i = 0; i  n) {
            if(++cur == m) {
                flag[q.front()] = false;
                q.pop();
                cur = 0;
            } else {
                q.push(q.front());
                q.pop();
            }
        }
        for(int i = 0; i < 2 * n; i++) {
            putchar(flag[i] ? 'G' : 'B');
            if((i + 1) % 50 == 0) putchar('\n');
        }
        putchar('\n');
        putchar('\n');
    }
    return 0;
}

作者：海岛Blog

hdu 约瑟夫环 stl

1024 个赞