AT_abc351_c [ABC351C] Merge the balls

题目描述

有一个空的队列和 $N$ 个球。第 $i$ 个球（$1\leq i\leq N$）的大小为 $2^{A_i}$。

接下来要进行 $N$ 次操作。
在第 $i$ 次操作中，将第 $i$ 个球加入队列的最右端，然后重复以下步骤：

1. 如果队列中的球数不超过 $1$，则结束本次操作。
2. 如果队列中从右数第 $1$ 个和第 $2$ 个球的大小不同，则结束本次操作。
3. 如果队列中从右数第 $1$ 个和第 $2$ 个球的大小相同，则将这两个球移除，并在队列最右端加入一个大小为“被移除的两个球大小之和”的新球。之后回到步骤 1，继续重复操作。

请在 $N$ 次操作结束后，输出队列中剩余球的数量。

输入格式

输入通过标准输入按以下格式给出。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出 $N$ 次操作结束后队列中剩余球的数量。

输入输出样例 #1

输入 #1

7
2 1 1 3 5 3 3

输出 #1

3

输入输出样例 #2

输入 #2

5
0 0 0 1 2

输出 #2

4

说明/提示

限制条件

• $1\leq N \leq 2\times 10^5$
• $0\leq A_i \leq 10^9$
• 输入均为整数

样例解释 1

操作过程如下：

• 第 $1$ 次操作后，队列中有 $1$ 个球，大小为 $2^2$。
• 第 $2$ 次操作后，队列中有 $2$ 个球，大小依次为 $2^2$、$2^1$。
• 第 $3$ 次操作后，队列中有 $1$ 个球，大小为 $2^3$。具体过程如下：
  • 在第 $3$ 次操作中加入第 $3$ 个球后，队列中球的大小依次为 $2^2, 2^1, 2^1$。
  • 由于最右边两个球大小相同，将它们移除，并加入一个大小为 $2^1+2^1=2^2$ 的球。此时队列中球的大小为 $2^2, 2^2$。
  • 再次发现最右边两个球大小相同，将它们移除，并加入一个大小为 $2^2+2^2=2^3$ 的球，队列中只剩下 $2^3$。
• 第 $4$ 次操作后，队列中有 $1$ 个球，大小为 $2^4$。
• 第 $5$ 次操作后，队列中有 $2$ 个球，大小依次为 $2^4$、$2^5$。
• 第 $6$ 次操作后，队列中有 $3$ 个球，大小依次为 $2^4$、$2^5$、$2^3$。
• 第 $7$ 次操作后，队列中有 $3$ 个球，大小依次为 $2^4$、$2^5$、$2^4$。

因此，最后队列中球的数量为 $3$，输出 $3$。

样例解释 2

操作过程如下：

• 第 $1$ 次操作后，队列中有 $1$ 个球，大小为 $2^0$。
• 第 $2$ 次操作后，队列中有 $1$ 个球，大小为 $2^1$。
• 第 $3$ 次操作后，队列中有 $2$ 个球，大小依次为 $2^1$、$2^0$。
• 第 $4$ 次操作后，队列中有 $3$ 个球，大小依次为 $2^1$、$2^0$、$2^1$。
• 第 $5$ 次操作后，队列中有 $4$ 个球，大小依次为 $2^1$、$2^0$、$2^1$、$2^2$。

因此，最后队列中球的数量为 $4$，输出 $4$。

由 ChatGPT 4.1 翻译