AT_abc340_c题解

bigclever · 2024-05-01 13:05:29 · 题解

贡献一个和目前所有题解都不一样的规律，而且代码实现非常简单。

以 n=13 的情况为例：

• 前 \lceil \log_2 n \rceil 层的数的和均为 n。因为在 x \gt 1 时，\lfloor \frac{x}{2} \rfloor+\lceil \frac{x}{2} \rceil=x。

• 可以发现前 \lfloor \log_2 n \rfloor 层的数都大于 1，所以这些数都是我们需要支付的金额。等到第 \lceil \log_2 n \rceil+1 层时所有数都已经小于等于 1 了，便无需再计算了。

• 所以重点在于第 \lceil \log_2 n \rceil 层。可以发现这一层里只有 1 和 2，所以我们可以算出这一层一共有 2^{\lfloor \log_2 n \rfloor} 个数，那么被计入答案的 2 即有 n-2^{\lfloor \log_2 n \rfloor} \times 1 个。

综上，答案即为 n \times \lfloor \log_2 n \rfloor + 2 \times (n-2^{\lfloor \log_2 n \rfloor})。