hdu 1276 士兵队列训练问题

简介: hdu 1276 士兵队列训练问题

士兵队列训练问题


Problem Description


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


Input


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


Output


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


Sample Input

2
20
40


Sample Output


1 7 19
1 19 37


新兵编号:1,2,3……n


出列规则:


1.一二报数,报到二的出列。出列编号:2,4,6……,剩余编号:1,3,5……


2.剩余新兵一二三报数,报到三的出列。出列编号:5,11,……,剩余编号1,3,7,9……


3.循环上述过程,直到剩余人数<=3


主要思路:


用链表


step1:正序or逆序建立一个建表,并给新兵编号


step2:当新兵num<=3时:输出链表


        否则:
         a.遍历第一次:一二报数,删除凡是报到二的。(count:报到二 or 三的标志。i:计数)。
         b.遍历第一次后就得判断num<=3是否成立。 成立:结束。不成立:改变报数标志,指针回到起点。
         c. 遍历第二次:一二三报数,删除凡是报到三的。             


step3:重复step2,直到b条件成立。结束循坏。


step4:输出链表


注:循环条件不能是while(num>3)。


代码1:用list


#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<algorithm>
#include<vector>
#include<list>
#include<stack>
#include<queue>
// #include<bits/stdc++.h>
using namespace std;
int main()
{
  int t,n;
  cin>>t;
  while(t--)
  {
    cin>>n;
    int k=2;
    list<int> mylist;
    list<int>:: iterator it;    // 定义迭代器
    for(int i=1;i<=n;i++) 
     {
      mylist.push_back(i);
     }
     // 出列操作 
     while(mylist.size()>3)
     {
      int num=1;
      for(it=mylist.begin();it!=mylist.end();){
        if(num++ %k==0)
          it=mylist.erase(it);
        else
          it++;
      }
      k==2?k=3:k=2;   // 切换报数的方式 2 或 3报数 
     }
     for(it=mylist.begin();it!=mylist.end();it++)
     {
      if(it!=mylist.begin())
        cout<<" ";
      cout<<*it;  
     }
     cout<<endl;
  }
  return 0;
}


代码2:用链表


#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
  int data;
  struct LNode *next;
}LNode, *LinkList;
LinkList CreateList_L(int num) //给新兵编号
{
  LinkList L, pt;
  L = (LinkList)malloc(sizeof(LNode));
  L->next = NULL;
  for (int i = num; i > 0; i--) //逆序建立链表
  {
    pt = (LinkList)malloc(sizeof(LNode));
    pt->data = i;
    pt->next = L->next;
    L->next = pt;
  }
  return L;
}
LinkList operate(LinkList &L, int num) //报数
{
  int count = 2, i = 1;
  LinkList pt;
  pt = L;
  while (true)
  {
    if (pt->next)
    {
      if (i == count)
      {
        pt->next = pt->next->next;//删除
        num--;
      }
      else
      {
        pt = pt->next;
      }
      i = i%count + 1; //一二报数或者一二三报数
    }
    else if (num <= 3)
    {
      break;
    }
    else
    {
      i = 1;
      count = 5 - count;
      pt = L;//回到开始
    }
  }
  return L;
}
void Print(LinkList L) //输出
{
  LinkList pt;
  pt = L->next;
  if (pt)
  {
    do
    {
      if (pt->next == NULL)
      {
        printf("%d", pt->data);
      }
      else
        printf("%d ", pt->data);
      pt = pt->next;
    } while (pt);
  }
}
int main()
{
  int n;
  scanf("%d", &n);
  while (n--)
  {
    int num;
    LinkList L;
    scanf("%d", &num);
    L = CreateList_L(num);
    if (num <= 3)
    {
      Print(L);
      printf("\n");
    }
    else
    {
      L = operate(L, num);
      Print(L);
      printf("\n");
    }
  }
  return 0;
}
相关文章
|
6月前
|
Java 测试技术
HDU-1233-还是畅通工程
HDU-1233-还是畅通工程
36 0
|
6月前
青蛙的约会—POJ1061
青蛙的约会—POJ1061
畅通工程 HDU - 1232
畅通工程 HDU - 1232
79 0
HDU1276士兵队列训练问题
HDU1276士兵队列训练问题
|
算法
HDU - 2063: 过山车
HDU - 2063: 过山车
143 0
|
Java 测试技术
HDU 1232 畅通工程
畅通工程 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 50540    Accepted Submission(s): 26968 Problem Description 某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。
1022 0
|
人工智能 Java C++
HDU 3785 寻找大富翁
寻找大富翁 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6716    Accepted Submission(s): 2492 Problem Description 浙江桐乡乌镇共有n个人,请找出该镇上的前m个大富翁.
1096 0
|
人工智能 算法 Java