题目意思:有N份申请表围城一圈,编号为逆时针编号,有两个人一个从逆时针走k步,另一个人顺时针走m,然后就有两个人所对应的申请书的编号,如果两个人走到同一个编号那么只要删除一个就好,如果不同删除两个,知道元素为空。
解题思路:我们很容易想到用循环队列来做,但是实现起来真的有点复杂,我们可以利用数组模拟,开两个数组,分别存储编号值,再开两个数组用来表示是否该位置被删除
begin1 begin2表示两个人的下一位置
注意事项:如果下一位置被删除了,那么我们要继续向下,就是要走有申请书的位置K步(或第二个人的m步);
代码1(数组模拟过程)
#include <iostream> #include <stack> #include <map> using namespace std; int p1[25] , p2[25];//两个数组分别存储两个人走的方向的编号,例如 p1={1,2....n} , p2={n , n-1 ...1}; int mark1[25] , mark2[25];//两个数组标记是否被删除,0没有,1有 int n, m ,k; int begin1 , begin2;//分别表示两个人的下一步开始位置,初始化为全为1 //初始化函数 void init(){ int i , j; memset(p1 , 0 , sizeof(p1)); memset(p2 , 0 , sizeof(p2)); memset(mark1 , 0 , sizeof(mark1)); memset(mark2 , 0 , sizeof(mark2)); //编号的赋值 for(i = 1 ; i <= n ; i++){ p1[i] = i; p2[i] = n-i+1; } } //第一个人走的函数 int find1(int begin , int n , int k){ int count = 0; while(count < k){ if(begin == n + 1)//如果超过n从新变成1 begin = 1; if(mark1[begin] == 0){//如果该位置没被删除 count++;//向前走一步 if(count == k)//如果走了k步就退出 break; } begin++;//begin每一次都要加,因为如果下一个是被删除了则继续向下 } return begin; } //第二个人走的函数(同上) int find2(int begin , int n , int m){ int count = 0; while(count < m){ if(begin == n + 1) begin = 1; if(mark2[begin] == 0){ count++; if(count == m) break; } begin++; } return begin; } //处理循环过程 void output(){ int count = 0; init(); int a, b;//a b是表示两个人的位置,不是编号 begin1 = 1 , begin2 = 1;//初始化两个人都是从他们方向的1处开始 while(count != n){ a = find1(begin1 , n, k); b = find2(begin2 , n, m); //cout<<"a:"<<a<<" "<<"b:"<<b<<endl; //如果两个人找到同一个值 if(p1[a] == p2[b]){ printf("%3d" , p1[a]); count++;//只删除一个 } if(p1[a] != p2[b]){ printf("%3d" , p1[a]); printf("%3d" , p2[b]); count += 2;//删除两个 } mark1[a] = 1; mark2[b] = 1; mark1[n-b+1] = 1; //注意第二个人走的位置,相对第一个人来说也是走过的 mark2[n-a+1] = 1;//注意第一个人走的位置,相对第二个人来说也是走过的 begin1 = a + 1;//指向下一个位置 begin2 = b + 1; if(count != n) cout<<","; } cout<<endl; } int main(){ int i , j; while(cin>>n>>k>>m){ if(n == 0 && k == 0 && m == 0) return 0; output(); } return 0; }
//list过的,迭代器的强大应用list的好处在于它的迭代器是一个环状的 #include <cstdio> #include <cstring> #include <iostream> #include <stack> #include <list> #include <algorithm> using namespace std; int n , k , m , mark; list<int>lis;//用来存储编号 list<int>::iterator it1;//it1指向第一个人的位置 list<int>::iterator it2;//it2指向第二个人的位置 //初始话函数 void init(){ int i; //把编号先插入 for(i = 1 ; i <= n ; i++) lis.push_back(i); it1 = lis.begin();//迭代器1指向开头 it2 = --lis.end();//迭代器2指向末尾 } //判断当前位置是否是在lis.end() inline void judge(){ if(it1 == lis.end()) ++it1;//对于it1则要编程lis.begin(); if(it2 == lis.end()) --it2;//对于it2则要变成lis.end(); } //第一个人的函数 int findp1(){ int count = 1; while(count != k){ it1++; count++; if(it1 == lis.end()) //如果当前位置到lis.end()就有在算一次 count--; } return *it1; } //第二个人的函数 int findp2(){ int count = 1; while(count != m){ --it2; count++; if(it2 == lis.end()) //如果当前位置到lis.end()就有在算一次 count--; } return *it2;; } //处理函数 void solve(){ int i ,j , p1 , p2, count = 0; init();//调用初始化函数 while(count != n){ p1 = findp1(); p2 = findp2(); if(p1 == p2){ printf("%3d" , p1); count++; if(count == n) break; it1 = lis.erase(it1); --it2;//对于it2只要减1即可往前 judge(); } if(p1 != p2){ printf("%3d%3d" , p1 , p2); count += 2; if(count == n) break; it1 = lis.erase(it1); if(*it1 == *it2)//如果出现当前位置刚好是下个人要删除的那么it1加加 ++it1; it2 = lis.erase(it2);//由于erase后指针后移,那么it2要减1 --it2; judge(); } if(count != n){//只要不是n输出逗号 printf(","); } }; cout<<endl; } //主函数 int main(){ while(scanf("%d%d%d" ,&n , &k , &m)){ lis.clear();//注意清空链表不然RE if(n == 0 && k == 0 && m == 0) break; solve(); } return 0; }
时间: 2024-09-20 08:40:02