首页 > 代码库 > 杭电1276 士兵队列训练问题

杭电1276 士兵队列训练问题

士兵队列训练问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3441    Accepted Submission(s): 1595


Problem Description
某部队进行新兵队列训练,将新兵从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向小序号方向靠拢,再从头开始进行一至三报数,凡报到三的出列,剩下的向小序号方向靠拢,继续从头开始进行一至二报数。。。,以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。

Input
本题有多个测试数据组,第一行为组数N,接着为N行新兵人数,新兵人数不超过5000。

Output
共有N行,分别对应输入的新兵人数,每行输出剩下的新兵最初的编号,编号之间有一个空格。

Sample Input
2 20 40

Sample Output
1 7 19
1 19 37

 

这个是用STL里的队列做的,不懂的可以了解一下STL,学会了这个可以直接拿来运用。

代码:

#include<stdio.h>
#include<queue>
using namespace std ;
queue<int> q ;
void remove(int x)
{
 int i = 1 ;
 while(q.front() != 0)
 {
  if(i%x != 0)//留下来的队伍
   q.push(q.front()) ;
  q.pop();//去掉队首
  i++ ;
 }
 q.pop();
 q.push(0) ;//把队尾的0去掉再在队尾加上0
}
int main()
{
 int N = 0 ;
 scanf("%d" , &N) ;
 while(N--)
 {
  int n = 0 ;
  scanf("%d",&n);
  int i = 0 ,j = 0 ;
  for(i = 1 ; i <= n ; i++ )
  {
   q.push(i) ;
  }
  q.push(0) ;
  int k = 1 ;
  while(q.size() > 4)//因为加上了0,所以长度小于4时就退出
  {
   if(k % 2)
    remove(2) ;//如过变换的次数为奇数则数1~2,踢掉2,否则数1~3,踢掉3
            else
    remove(3) ;
   k++;
  }
  j = 0 ;
  while(!q.empty())
  {
      if(q.front() > 0)
   {
    if(j)
     printf(" ");
    j = 1 ;
    printf("%d", q.front());
   }
   q.pop() ;
  }
  printf("\n") ;
 }
 return 0 ;
}