题目
问题描述
思路
这个题目的坑点在于一定要记得考虑k=1的情况，我第一次提交就没有考虑k=1，然后提示运行超时90分。我唯一想到的原因就是for循环太多了或者使用最基本的数组，数据处理显得会很复杂？解决办法大概就是缩减for循环，再不行就只能更改成vector或者queue了。（毕竟测试样例和自己试了几个例子都没问题，所以一定一定要记得考虑边界情况鸭！）后来百度一下，刚好碰到有个同学也是一样的问题导致运行超时90分，也给出了提示（https://blog.csdn.net/zhaoshuling1109/article/details/81232297），感谢！而且这位同学也给出了除基本数组外的别的解法，这里就不搬运啦。就只给出自己最渣渣的解法。
题解
#include<iostream> using namespace std; int main(){ int n,k; scanf("%d %d",&n,&k); int child[n]; int num=n;//剩余人数 int cur=1; for(int i=1;i<n+1;i++){//初始化为顺序编号 child[i]=i; } if(k==1){ printf("%d",n); } else{ while(num!=1){ for(int i=1;i<n+1;i++){ //printf("1----child[%d]=%d;\n",i,child[i]); if(child[i]!=0){ /*if((child[i]%k==0) || (child[i]%10==k)){//如果报到相应数字，小朋友淘汰，则置零 printf("2----child[%d]=0;\n",i); child[i]=0; num--; } else{ child[i]=cur; printf("3----child[%d]=%d;\n",i,cur); if((child[i]%k==0) || (child[i]%10==k)){//如果报到相应数字，小朋友淘汰，则置零 printf("4----child[%d]=0;\n",i); child[i]=0; num--; } }*/ child[i]=cur; //printf("3----child[%d]=%d;\n",i,cur); if((child[i]%k==0) || (child[i]%10==k)){//如果报到相应数字，小朋友淘汰，则置零 //printf("4----child[%d]=0;\n",i); child[i]=0; num--; } cur++; } if(num==1){ break; } } } for(int i=1;i<n+1;i++){ if(child[i]!=0){ printf("%d",i); } } } return 0; }
忍不住再给出一个我觉得非常好的解法，以及基本要忘了数据结构的我想到却实现不到的做法。
利用queue队列，“先入先出”（谁先被push，谁先被pop）。因为是小朋友是循环报数，按顺序将小朋友放入队列，front()取出最早被压入队列的那个。如果当前处理的值（小朋友）是出局的那个，那么取出来后，就不再加入队列中了；否则将他压入队列。这种做法就是不需要将小朋友与他报过的数一一对应起来，而是用一个num来表示取出某个小朋友，对应的数字。
顺便复习一下队列的内容：
queue.empty();//队列为空，空输出1 queue.size(); queue.push();//队尾插入一个元素(队尾) 5 4 3 2 1(队首) queue.pop();//删除队列第一个元素 5 4 3 2 queue.front();//输出队列第一个元素 2 queue.back();//输出队列最后元素 5
参考了这位同学的做法（https://blog.csdn.net/qq_16234613/article/details/79006514）
#include<iostream> #include<queue> using namespace std; int main(){ int n,k; int num=1; scanf("%d %d",&n,&k); queue<int> list; for(int i=1;i<n+1;i++){ list.push(i); } while(list.size()>1){ int top=list.front(); list.pop(); if((num%k!=0) && ((num%10)!=k)){ list.push(top); } num++; } printf("%d",list.front()); return 0; }
原文：https://www.cnblogs.com/lyeeer/p/11461445.html