隊列水題

（另附約瑟夫環士兵隊列訓練問題 來源： ​​https://cn.vjudge.net/contest/268984#problem/B​​ 某部隊進行新兵隊列訓練，将新兵從一開始按順序依次編号，并排成一行橫隊，訓練的規則如下：從頭開始一至二報數，凡報到二的出列，剩下的向小序号方向靠攏，再從頭開始進行一至三報數，凡報到三的出列，剩下的向小序号方向靠攏，繼續從頭開始進行一至二報數。。。，以後從頭開始輪流進行一至二報數、一至三報數直到剩下的人數不超過三人為止。

Input：

本題有多個測試資料組，第一行為組數N，接着為N行新兵人數，新兵人數不超過5000。

Output：

共有N行，分别對應輸入的新兵人數，每行輸出剩下的新兵最初的編号，編号之間有一個空格。

//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;
}