题目地址

http://exercise.acmcoder.com/online/online_judge_ques?ques_id=1650&konwledgeId=136

题目描述

某大学开学进行军训队列训练，将学生从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列剩下的依次向前靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的依次向前靠拢，继续从头开始进行一至二报数。。。以后每次从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。

题目分析

这道题，在赛码网站被归类到了动态规划中，然而解题并没有用到动态规划，而是模拟的思想。也就是说通过程序，模拟报数排队的过程。

可以使用一个vector map(num,false)数组来标识原始序列中，该位置的学生是否被淘汰。

对于从1数到2的情况，
对于每一次报数，使用k来计数。
初始化为0，当遇到map[i]为false的，则k++。
当k==2时，“淘汰”该学生，map[i]=true，并且k置零等待下一次排序。

对于从1数到3的情况与之类似。

代码

#include
#include
using namespace std;
int main(){int n,num;cin>>n;for(int i=0;icin>>num;//模拟程序开始int left = num;vector<bool> map(num+1,false);int k;while(1){if(left > 3){//排除序号为2的k = 0;for(int i=1;i<=num;i++){if(map[i] == false){k++;if(k == 2){map[i] = true;left--;k = 0; }}} }else{break;}if(left > 3){//排除序号为3的 k = 0;for(int i=1;i<=num;i++){if(map[i] == false){k++;if(k == 3){map[i] = true;left--;k = 0;}}} }else{break;}}for(int i=1;i<=num;i++){if(map[i] == false){cout<" ";}}cout<return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！