P13405 [GCJ 2010 #3] Hot Dog Proliferation
题目描述
有若干热狗摊贩在一条很长的东西向街道的各个路口（交叉口）上卖热狗。问题在于，可能有多个摊贩在同一个路口，这样他们就会互相抢生意。不过事情还有转机！热狗摊贩们有一个计划。
如果某个路口上有两个或更多摊贩，那么恰好有两位摊贩可以进行一次移动，具体如下：
- 一位摊贩向东移动到下一个路口。
- 另一位摊贩向西移动到下一个路口。
请注意，这条街道非常长，所以不用担心会没有路口可去。给定所有热狗摊贩的初始位置，请你计算，最少需要多少次移动，才能让所有摊贩都分开（即每个摊贩都在不同的路口）。
例如，假设街道上各个路口的热狗摊贩数量从西到东依次如下：
```
... 0 0 2 1 2 0 0 ...
```
那么摊贩们可以通过三次移动分开，如下所示：
```
... 0 0 2 1 2 0 0 ...
|
+--- 在这里进行一次移动
... 0 1 0 2 2 0 0 ...
|
+--- 在这里进行一次移动
... 0 1 1 0 3 0 0 ...
|
+--- 在这里进行一次移动
... 0 1 1 1 1 1 0 ...
```
输入格式
每个路口用一个整数标号，可以为正也可以为负。对于每个 $i$，路口 $i+1$ 表示比路口 $i$ 更靠东的下一个路口。我们将使用这种标号方式来描述输入文件中的路口。
输入文件的第一行包含测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行包含一个整数 $C$，表示初始状态下至少有一个热狗摊贩的路口数量。接下来的 $C$ 行，每行包含两个用空格分隔的整数 $P$ 和 $V$，表示在路口 $P$ 上有 $V$ 个摊贩。
输出格式
对于每组测试数据，输出一行，格式为 "Case #$x$: $M$"，其中 $x$ 是测试用例编号（从 1 开始），$M$ 是将所有摊贩分开所需的最小移动次数。
说明/提示
**数据范围**
- $1 \leq T \leq 50$。
- $1 \leq C \leq 200$。
- 所有 $P$ 的取值范围为 $[-1000000, 1000000]$。
- 每组测试数据中，所有 $P$ 互不相同，并且按递增顺序给出。
- 所有 $V$ 都为正整数。所有 $V$ 的和的限制见下文。
- 总是可以在有限步内将所有摊贩分开。
**小数据范围（6 分，测试集 1 - 可见）**
- 每组测试数据中热狗摊贩总数不超过 200。
**大数据范围（22 分，测试集 2 - 隐藏）**
- 每组测试数据中热狗摊贩总数不超过 100000。
由 ChatGPT 4.1 翻译