Game Rooms

题意翻译

## 题意 一个 $N$ 层的大楼,每层只有一个游戏室,可以设置一个乒乓球桌或游泳池。第 $i$ 层有 $T_i$ 个人喜欢乒乓球和 $P_i$ 个人喜欢游泳。 现在要求使每个人到最近的喜欢的类型的活动室的距离的**和**最小,且这栋大楼要有至少一个乒乓球桌和至少一个游泳池。 这里的距离指楼层差的绝对值。例如,如果一个人到他喜欢的类型的游戏室位于同一楼层,则为 $0$;如果所需类型的最接近的游戏室正好在该员工的上方或下方一层,则为 $1$,以此类推。 ## 输入格式 第一行给出数据组数 $T$( $1\leq T\leq 100$)。接下来对于每组数据,首先一行给出 $N$( $2\leq N\leq 4000$),代表该大楼一共有多少层;接下来 $N$ 行第 $i$ 行给出两个整数 $T_i, P_i$( $1\leq T_i, P_i\leq 10^9$),代表第 $i$ 层的人数,意义同题意 ## 输出格式 对于第 $x$ 组( $x$ 从 $1$ 开始标号)数据的答案 $y$,在第 $x$ 行输出 `Case #x: y` ## 样例解释 在第一层设置乒乓球桌,在第二层设置游泳池。这样 $5$ 个人要从第一层走到第二层, $4$ 个人要从第二层走到第一层,距离和为 $9$ Translated by @Piwry

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=862&page=show_problem&problem=4874 [PDF](https://uva.onlinejudge.org/external/129/p12991.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12991/63aa067d4138986d9a23ff252b6eb4916348642c.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12991/e5fdfa54c8b561dc571f141619fb22140899434e.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12991/a8eb0f3a94edced7532a0728fb5b04ba050a0d96.png)

输入输出样例

输入样例 #1

1
2
10 5
4 3

输出样例 #1

Case #1: 9