1082 . C.分堆問題
TopCoder
Tags
Description
有n堆石頭，每堆石頭都有可能混雜著一些黑色石頭或白色石頭。現在請問最少要移動多少個石頭，才能讓每一堆石頭要嘛全是黑色，要嘛全是白色。所謂的移動一個石頭，是指把其中一堆的其中一個石頭搬到另一堆去，你不能丟掉、敲碎、吃掉或者用任何手段銷毀任何一顆石頭，你也不能把石頭移到別的空地去(沒有別的空位啦！)。
Input Format
輸入可能包含多筆測試資料。每一筆測試資料的第一列有一個正整數n (1<=n<=1,000,000)，代表石頭的堆數，接下來的n列每列有兩個整數 Bi和 Wi，代表此堆黑色石頭和白色石頭的個數。當n=0時代表輸入結束。每一組測試資料中石頭的總數一定小於231。
Output Format
對於每組測試資料，請輸出一個整數代表所需移動的最少石頭個數。如果不管移動多少石頭都沒辦法達成目標，請輸出-1。
Sample Input 1
3
2 3
4 1
0 5
3
2 3
1 2
0 4
0
2 3
4 1
0 5
3
2 3
1 2
0 4
0
Sample Output 1
3
4
4
Hints
對於第一筆測試資料：把第一堆的黑色石頭搬到第二堆，然後把第二堆的白色石頭搬到第三堆。至少需要搬動3顆石頭。
Problem Source
原TIOJ1082 / Problem Setter: Tmt。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 50 |
| 2 | 1 | 50 |