队列水题
（另附约瑟夫环：https://blog.csdn.net/nuoyanli/article/details/84110081）
士兵队列训练问题 来源： https://cn.vjudge.net/contest/268984#problem/B
某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。。。，以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。
Input：
本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。
Output：
共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。
Sample Input：
2
20
40
Sample Output：
1 7 19
1 19 37
题意：按描述的出队入队（标记数组就好不用删除元素）
思路：队列模拟（这道题在开始的时候wa了我一发，就是因为没有将n>3和<=3来分开考虑；如果小于等于三的话就不用再进行报数出列了，就直接输出就行了！这一点我用试数的方法就解决了，这一点体现了试数的重要性！ ）
代码：
//queue模拟
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
queue<int>q;//队列定义，放在里面是为了每次清空队列
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
q.push(i);//把每个人的编号都按顺序压入队列中
}
int p=1,x,k;
while(q.size()>3)//如果还有超过三个人,继续进行编号和排除等操作
{
x=q.size();//目前一共有多少人
if(p&1)//如果是第奇数次，那么就是从 1 到 2 编号
{
for(int i=0;i<x/2;++i)//循环操作
{
k=q.front();//<span style="font-family: Arial, Helvetica, sans-serif;">取出编号为 1 的</span>
q.push(k);//把编号为 1 的放后边，入队
q.pop();//抛弃编号为 1 （已经放后面了，这个就不需要了）
q.pop();//现在弹出的编号为 2 ，抛弃...
}
if(x&1)
{
k=q.front();//如果刚开始的时候为奇数个，那么最后还有一个人没被循环过....
q.push(k);//放队尾
q.pop();//抛弃.....
}
}
else//第偶数次，那就是从 1 到 3 编号
{
for(int i=0;i<x/3;++i)
{
k=q.front();q.push(k);//处理编号为 1 ，处理方式和前面一样.....
q.pop();
k=q.front();q.push(k);//处理编号为 2
q.pop();
q.pop();//抛弃编号为 3 的
}
while(x%3!=0)//这里和前面的道理一样，防止有人未处理完
{
--x;
k=q.front();q.push(k);//处理剩余的那几个....
q.pop();
}
}
++p;
}
while(q.size()!=1)//输出，这样是为了控制格式...
{
printf("%d ",q.front());
q.pop();
}
printf("%d\n",q.front());
}
return 0;
}
//数组模拟1
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int a[5005],b[5005];
int main()
{
int T,n,m,i,j,k,t,d[5];
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
//n=T;
for(i=1;i<=n;i++)//这里面的数组a用来存放士兵在队列中的编号（新组成的会有新的编号）
{
a[i]=i;
b[i]=1;//数组b用来如果在队列中，则用1来表示，如果出列，则用0来表示
}
t=n;//因为这里面的n会在计算中发生变化，所以要重新赋值，用另一个变量代替它发生变换！
if(n>3)//当n>3的时候，因为需要出列，所以按照题意执行就可以了，记住，执行过之后
for(j=1;j<=n;j++)//士兵的顺序不发生改变，但是序号发生了变化！，所以在他们每出列一次要重新
{
for(i=1,k=0;i<=n;i++)//给士兵进行赋值操作！但是最后需要输出原来的编号！
{
if(a[i]%2==0&&b[i])//这并不难，因为标记数组的下标你又没有发生改变，所以到时候
{
b[i]=0;//将数组b中对应是1的元素的下标输出来就行了！
t--;
}
else if(b[i])
{
k++;
a[i]=k;
}
}
if(t<=3)
break;
for(i=1,k=0;i<=n;i++)
{
if(a[i]%3==0&&b[i])
{
b[i]=0;
t--;
}
else if(b[i])
{
k++;
a[i]=k;
}
}
if(t<=3)
break;
}
for(i=1,j=0;i<=n;i++)//因为题上格式要求比较严格，所以要进行赋值到一个数组中，进行
{
if(b[i])//比较规格的输出！
d[j++]=i;
}
if(t==3)
printf("%d %d %d\n",d[0],d[1],d[2]);
else if(t==2)
printf("%d %d\n",d[0],d[1]);
else if(t==1)
printf("%d\n",d[0]);
}
return 0;
}
//数组模拟2
#include<iostream>
using namespace std;
int f[5005];
int main()
{
int t;
int n,i;
while(cin>>t)
{
while(t--)
{
cin>>n;
for(i=1;i<=n;i++)
f[i]=i;
int t;
if(n<=3)
{
printf("1");
for(i=2;i<=n;i++)
printf(" %d",i);
printf("\n");
continue;
}
while(1)
{
int leap=0;
for(i=1;i<=n;i++)
{
if(f[i]!=-1)
{
leap++;
}
if(leap==2)
{
leap=0;
f[i]=-1;
}
}
t=0;
for(i=1;i<=n;i++)
if(f[i]!=-1)
t++;
if(t<=3)
break;
leap=0;
for(i=1;i<=n;i++)
{
if(f[i]!=-1)
leap++;
if(leap==3)
{
f[i]=-1;
leap=0;
}
}
t=0;
for(i=1;i<=n;i++)
if(f[i]!=-1)
t++;
if(t<=3)
break;
}
for(i=1;i<=n;i++)
if(f[i]!=-1)
{
printf("%d",f[i]);
break;
}
i++;
for(;i<=n;i++)
if(f[i]!=-1)
printf(" %d",f[i]);
printf("\n");
}
}
return 0;
}
京公网安备 11010502036488号