### 题目

给定一个从 1 到 n 排序的整数列表。
首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。
第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。
我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
返回长度为 n 的列表中，最后剩下的数字。

<!--more-->

### 示例

```tex
输入：
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

输出：
6
```

### 解答

暴力模拟超时，看了一下别人的思路。

通过观察用例，我们可以得到以下规律：

1. 经历的回合数应该是 $$\lfloor \log_2n \rfloor + 1$$
2. arr 数组永远是一个等差数列
3. arr 数组的数目，每次减少一半（向下取整）
4. 公差每次翻倍

我们知道一个等差数列可以由 a0（首项）, d（公差）, n（数列元素个数）三个参数来定义。

综合以上规律，我们知道每次删除后，以上三个参数每次应该这样变化

> - d → 2d
> - n → n/2
> - a0→a0 或者 a0→a0+d

大体上来说这道题目就是这样，其它细节可以看代码。

如何决定 a0 的变化？当删除数字时，存在以下四种情况：

1. 从左向右删除，总共有奇数个数字（第一位要删掉，最后一位要删掉）
2. 从左向右删除，总共有偶数个数字（第一位要删掉，最后一位不用删掉）
3. 从右向左删除，总共有奇数个数字（第一位要删掉，最后一位要删掉）
4. 从右向左删除，总共有偶数个数字（第一位不用删掉，最后一位要删掉）

只有情况 4 才会出现`a0→a0`，其余都是`a0→a0+d`

### 代码

```c++
int lastRemaining(int n) {
    int num_amount = n;
    int loop_cnt = 0;
    int a0 = 1, d = 1;
    while (num_amount != 1) {
        // 奇数个数字
        if (num_amount % 2 == 1) {
            a0 = a0 + d;
        }
            // 偶数个数字
        else if (num_amount % 2 == 0) {
            bool left_to_right = (loop_cnt % 2 == 0);
            if (left_to_right) {
                a0 = a0 + d;
            } else
                a0 = a0;
        }
        loop_cnt++;
        d *= 2;
        num_amount /= 2;
    }
    return a0;
}
```

### 参考文章

[C++ 数学 + 找规律 - 消除游戏 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/elimination-game/solution/c-shu-xue-by-qian2-60yk/)