当前位置：首页 > news >正文

hdu 4841 圆桌问题（STL vector）

news 来源：原创 2024/5/7 8:46:15

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

Source

AHOI1999

题意：中文题就不用了

思路：

首先需要一个vector保存每个人，然后是一个vis数组来标记。

找n个人，所以循环n次。定义一个cnt=0，每一次cnt+=m-1,。

如果cnt<=当前的总人数，则将v.erase（v.begin（）+cnt），vis【v.【cnt】】=1，当前人数-1；

如果cnt>=当前人数，cnt%=（当前的总人数），v.erase（v.begin（）+cnt），vis【v.【cnt】】=1，当前人数-1；

Vis【i】=1 为B，vis【i】=0为G

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<vector>
 5 #include<set>
 6 #include<algorithm>
 7 using namespace std;
 8 #define N 100000
 9 int n,m;
10 vector<int> v;
11 int vis[N];
12 int main()
13 {
14     while(scanf("%d%d",&n,&m)==2)
15     {
16         v.clear();
17         memset(vis,0,sizeof(vis));
18         int now=2*n;//总共的人数，下标从0开始 
19         
20         for(int i=0;i<now;i++)//初始化vector数组 
21           v.push_back(i);
22           
23         int cnt=0;  
24           for(int i=0;i<n;i++)
25           {
26               cnt=cnt+m-1;//当前的坏人
27             if(cnt<now)
28             {
29                 vis[v[cnt]]=1;//将这个坏人标记为1 
30                 v.erase(v.begin()+cnt);
31             } 
32             else 
33             {
34                 cnt=cnt%now;
35                 vis[v[cnt]]=1;//将这个坏人标记为1 
36                 v.erase(v.begin()+cnt);
37             }
38             now--;
39           }
40           
41           for(int i=0;i<2*n;i++)
42           {
43               if(i%50==0 && i!=0)
44                   printf("\n");
45               if(vis[i])
46                 printf("B");
47                  else 
48                    printf("G");
49           }
50           printf("\n");
51           printf("\n");
52           
53 
54         
55     }
56     return 0;
57 }