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