蓝桥杯算法训练VIP-筛选号码

题目

题目链接

题解

模拟。

大部分人一开始想法应该都是纯模拟，就是一开始 n n n个数，遍历一遍报3的删除掉，不停地进行直到只有一个人了。有人想用vector，调用删除函数进行删除操作；有人想用数组模拟，但是不知道如何实现删除，所以采用一个vis数组表示是否某个人是否出局，但是这样每次都要遍历n个人，不确定会不会超时。

所以 我来讲一下我用数组模拟的方法。

我只用数组的前 c n t cnt cnt位，什么意思呢？ 每次我都去遍历前 c n t cnt cnt位，这前 c n t cnt cnt位存的都是没出局的人的编号；因为会有人出局，人数会发生变化，因此 c n t cnt cnt也是变化的。 对于前 c n t cnt cnt个位，只要 c n t cnt cnt不是1，就说明还没结束，我们就让这 c n t cnt cnt个人报数，报到3的出局，如何体现出局呢？ 我们再用一个变量 n e w c n t newcnt newcnt作为临时变量，用于统计在前 c n t cnt cnt个人的这轮报数中，没报到3的有多少个，即未出局的。在遍历的过程中，我们将未出局的人的编号写回到以 n e w c n t newcnt newcnt为下标的数组中（这个数组还是最初那个数组，即前 c n t cnt cnt表示没出局的人的编号的数组），这一定是不会覆盖我们未遍历过的人的编号的，这点可以完全放心。当一轮遍历结束之后，数组中的前 n e w c n t newcnt newcnt个人就是这轮结束后还剩下的人的编号了，之后我们再将 n e w c n t newcnt newcnt赋值回 c n t cnt cnt中，因为 c n t cnt cnt才是表示数组前多少个人未出局的变量，而 n e w c n t newcnt newcnt只是用于临时统计的变量，再将 n e w c n t newcnt newcnt赋值为0，准备下一轮统计。 最后输出的就是数组中的第一个。

核心就一点，数组的前 c n t cnt cnt个人是未出局的，虽然数组中的编号数量还是n个，但是我们需要用的，或者说是有效的就是前 c n t cnt cnt个。每一轮都将被淘汰的人忽略，将留下的人的编号从数组的第一个位置开始赋值，这样就保证了前面的都是未出局的。

代码

#include
using namespace std;
const int N = 1e4+10;

int a[N], cnt, newcnt, num=1; // cnt存当前有多少个人报数   newcnt报完这一轮还有多少人   num每个人报的数是多少 

int main()
{
	cin>>cnt;
	
	for(int i = 1;i