圆桌问题vector

超、凢脫俗 2023-07-15 13:28 22阅读 0赞

### 圆桌问题 ###

*   *  题目：

## 题目： ##

> 圆桌问题 Time Limit: 3000/1000 MS (Java/Others) Memory Limit:  
> 65535/32768 K (Java/Others) Total Submission(s): 7789 Accepted  
> Submission(s): 2814
> 
> 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

学习vector的例题  
我的代码（有详细注释）：

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        
        vector < int > table;
        int n,m;
        while(~scanf("%d %d",&n,&m)){
        
            table.clear();  //清空
            for(int i=0; i<2*n; i++)
                table.push_back(i);  //初始化
    
            int pos = 0;  //记录当前位置
            for(int i=0; i<n; i++){
          //处死n个人
                pos = (pos+m-1) % table.size();
                //圆桌是个环，我们可以认为是很多很多个一样的数组，相邻接着
                table.erase(table.begin() + pos);  //table里把赶走的人去掉,人数减一
            }
    
            int j = 0;
            for(int i=0; i<2*n; i++){
          //打印预先安排的座位
                if(!(i%50) && i)
                    //实现50个字母换一行（注意i=0时不应该换行，所以&&i）
                    cout<<endl;
                if(j<table.size() && i==table[j]){
        
                    //因为i是从小到大遍历的，
                    //而table里的元素我们初始化时包括去掉某些元素，移动过程中，也是保持的从小到大的次序不变的
                    //所以可以只是遍历i，自然就是先匹配上较小的table[j]
                    j++;
                    cout<<"G";  //table中留下的都是好人
                }else
                    cout<<"B";
            }
            cout<<endl<<endl;  //相邻数据组间留一个空行
        }
        return 0;
    }