Merge Slimes

题目描述

Initially, there are $N$ sizes of slimes.
Specifically, for each $1\leq i\leq N$, there are $C_i$ slimes of size $S_i$. Takahashi can repeat slime synthesis any number of times (possibly zero) in any order.
Slime synthesis is performed as follows.

Choose two slimes of the same size. Let this size be $X$, and a new slime of size $2X$ appears. Then, the two original slimes disappear.

Takahashi wants to minimize the number of slimes. What is the minimum number of slimes he can end up with by an optimal sequence of syntheses?

输入格式

The input is given from Standard Input in the following format: $N$ $S_1$ $C_1$ $S_2$ $C_2$ $\vdots$ $S_N$ $C_N$

输出格式

Print the minimum possible number of slimes after Takahashi has repeated the synthesis.

3
3 3
5 1
6 1

3

3
1 1
2 1
3 1

3

1
1000000000 1000000000

13

提示

$1\leq N\leq 10^5$ $1\leq S_i\leq 10^9$ $1\leq C_i\leq 10^9$ $S_1,S_2,\ldots,S_N$ are all different. All input values are integers.最初，有三个大小为 $3$ 的史莱姆，一个大小为 $5$ 的史莱姆，和一个大小为 $6$ 的史莱姆。
Takahashi 可以按如下方式进行两次合成：

首先，选择两个大小为 $3$ 的史莱姆进行合成。此时会剩下一个大小为 $3$ 的史莱姆，一个大小为 $5$ 的史莱姆，和两个大小为 $6$ 的史莱姆。 接着，选择两个大小为 $6$ 的史莱姆进行合成。此时会剩下一个大小为 $3$ 的史莱姆，一个大小为 $5$ 的史莱姆，和一个大小为 $12$ 的史莱姆。

无论他如何从初始状态重复合成，都无法将史莱姆的数量减少到 $2$ 或更少，所以应当输出 $3$。
他不能进行合成。

标签: AtCoder|abc323D

来源

AtCoder|abc323D