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

队列_23约瑟夫问题+_24猫狗收容所

news 2025/8/25 18:26:40

约瑟夫问题
n 个小孩围坐成一圈，并按顺时针编号为1,2,…,n，从编号为 p 的小孩顺时针依次报数，由1报到m ，当报到 m 时，该小孩从圈中出去，然后下一个再从1报数，当报到 m 时再出去。如此反复，直至所有的小孩都从圈中出去。请按出去的先后顺序输出小孩的编号。
Input
每行是用空格分开的三个整数，第一个是n,第二个是p,第三个是m (0 < m,n < 300)。最后一行是:
0 0 0
Output
按出圈的顺序输出编号，编号之间以逗号间隔。
Sample Input
8 3 4
0 0 0
Sample Output
6,2,7,4,3,5,1,8

#include<bits/stdc++.h>
using namespace std;
//队列 
int main(){int n,p,m;while(cin>>n>>p>>m){queue<int> children;if(n==0 && p==0 && m==0){break;}for(int i=1;i<=n;i++){children.push(i);}for(int i=1;i<p;i++){children.push(children.front());children.pop();}while(!children.empty()){for(int j=1;j<m;j++){children.push(children.front());children.pop();}if(children.size()!=1){cout<<children.front()<<",";}else{cout<<children.front();}children.pop();}}return 0;
}

猫狗收容所
有家动物收容所只收留猫和狗，但有特殊的收养规则，收养人有两种收养方式：
第一种为直接收养所有动物中最早进入收容所的
第二种为选择收养的动物类型（猫或狗），并收养该种动物中最早进入收容所的。

给定一个操作序列代表所有事件。
若第一个元素为1，则代表有动物进入收容所，第二个元素为动物的编号，正数代表狗，负数代表猫；
若第一个元素为2，则代表有人收养动物，第二个元素若为0，则采取第一种收养方式，若为1，则指定收养狗，若为-1则指定收养猫。

请按顺序返回收养的序列。
若出现不合法的操作，即没有可以符合领养要求的动物，则将这次领养操作忽略。

输入：第一个是n，它代表操作序列的次数。接下来是n行，每行有两个值m和t，分别代表题目中操作的两个元素。

输出：按顺序输出收养动物的序列，编号之间以空格间隔。

#include<bits/stdc++.h>
using namespace std;
//队列 
int main(){int n,m,t;//两个队列，一个是猫，一个是狗//如何得知最早进入收容所的动物//解决方法：三个队列：不现实，当猫或狗被领养的时候，总的队列没办法删除 //解决办法(新)： queue<int> cat;queue<int> dog;int counter=0;cin>>n;while(n--){cin>>m>>t;if(m==1){if(t>0){counter++;dog.push(counter);dog.push(t);}else if(t<0){counter++;cat.push(counter);cat.push(t);}}else if(m==2){if(t==0){if(!dog.empty() && !cat.empty()){if(dog.front()<cat.front()){dog.pop();cout<<dog.front()<<" ";dog.pop();}else{cat.pop();cout<<cat.front()<<" ";cat.pop();	}}else if(!cat.empty() && dog.empty()){cat.pop();cout<<cat.front()<<" ";cat.pop();				}else if(cat.empty() && !dog.empty()){dog.pop();cout<<dog.front()<<" ";dog.pop();				}}else if(t==1){if(!dog.empty()){dog.pop();cout<<dog.front()<<" ";dog.pop();					}}else if(t==-1){if(!cat.empty()){cat.pop();cout<<cat.front()<<" ";cat.pop();}}}}return 0;
}