小球淘汰（入门版）

题目描述

桌面上有 n 个小球，从左到右排成一列。

每个小球都有一个编号，编号从左到右依次为：

1 2 3 ... n

小明每天都会进行一次淘汰操作。

每天操作规则如下：

1. 从当前小球队列的最左侧开始扫描；
2. 第 1 个、第 3 个、第 5 个……位置上的小球会被淘汰；
3. 没有被淘汰的小球按照原来的相对顺序向左移动，重新排列成一列；
4. 第二天继续对新的队列进行相同操作。

请你计算：

经过多少天，所有小球都会被淘汰？

---

输入格式

输入一个整数：

n

表示小球的数量。

---

输出格式

输出一个整数：

ans

表示所有小球全部被淘汰所需要的天数。

---

数据范围

1 ≤ n ≤ 10000

---

样例解释

输入

8

初始状态：

1 2 3 4 5 6 7 8

---

第 1 天

从左到右扫描：

位置：

1 2 3 4 5 6 7 8

淘汰：

1 3 5 7

剩余：

2 4 6 8

---

第 2 天

重新排列后：

2 4 6 8

淘汰第：

1 3

个小球：

也就是：

2 6

剩余：

4 8

---

第 3 天

当前：

4 8

淘汰：

4

剩余：

8

---

第 4 天

当前：

8

淘汰：

8

所有小球被淘汰。

所以答案：

4

---

输出

4

---

解题提示

本题要求模拟每天的小球变化过程。

可以使用两个数组：

• a：保存当前剩余的小球；
• b：保存下一天剩余的小球。

每一天：

1. 遍历当前数组；
2. 判断当前位置是否需要淘汰；
3. 没有淘汰的小球加入新数组；
4. 用新数组替换旧数组。

---

样例数据

样例1

输入：

1

输出：

1

解释：

只有一个小球，第一天直接被淘汰。

---

样例2

输入：

5

过程：

第一天：

1 2 3 4 5

淘汰：

1 3 5

剩余：

2 4

第二天：

淘汰：

2

剩余：

4

第三天：

淘汰：

4

输出：

3

测试点编号	n	难度层级	特殊性质	设计目的
1		弱数据	最小正整数	检查只执行 1 天的边界
2, 3			一奇一偶	检查奇偶长度下 floor(len / 2) 的处理
4, 5		正常数据	2 的幂及其后继	区分临界值附近天数是否正确
6, 7	7, 8		2 的幂前一位及 2 的幂	检查 7 -> 3天、8 -> 4天 的跳变
8, 9	15, 16			检查较大临界点的天数跳变
10	31		2 的幂前一位	检查连续折半到 0 的边界
11	1024	极限数据	较大 2 的幂	检查多轮循环稳定性
12	10005		数组容量上界	检查最大安全输入规模