Java程序練習-合並果子

合並果子
時間限制: 10000ms內存限制: 65536kB
描述
在一個果園裡，多多已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。
    每一次合並，多多可以把兩堆果子合並到一起，消耗的體力等於兩堆果子的重量之和。可以看出，所有的果子經過n-1次合並之後，就只剩下一堆了。多多在合並果子時總共消耗的體力等於每次合並所耗體力之和。
    因為還要花大力氣把這些果子搬回家，所以多多在合並果子時要盡可能地節省體力。假定每個果子重量都為1，並且已知果子的種類數和每種果子的數目，你的任務是設計出合並的次序方案，使多多耗費的體力最少，並輸出這個最小的體力耗費值。
    例如有3種果子，數目依次為1，2，9。可以先將1、2堆合並，新堆數目為3，耗費體力為3。接著，將新堆與原先的第三堆合並，又得到新的堆，數目為12，耗費體力為12。所以多多總共耗費體力=3+12=15。可以證明15為最小的體力耗費值。
輸入
輸入文件fruit.in包括兩行，第一行是一個整數n(1<＝n<=10000)，表示果子的種類數。第二行包含n個整數，用空格分隔，第i個整數ai(1<＝ai<=20000)是第i種果子的數目。
輸出
輸出文件fruit.out包括一行，這一行只包含一個整數，也就是最小的體力耗費值。輸入數據保證這個值小於231。
樣例輸入
3
1 2 9
樣例輸出
15
提示
對於30％的數據，保證有n<=1000： 對於50％的數據，保證有n<=5000； 對於全部的數據，保證有n<=10000。
參考代碼

1. import java.io.BufferedReader;  
2. import java.io.IOException;  
3. import java.io.InputStreamReader;  
4. import java.util.Iterator;  
5. import java.util.Map;  
6. import java.util.Set;  
7. import java.util.TreeMap;  
8. public class Main {  
9.     public static Map<Integer,Integer>map = new TreeMap<Integer,Integer>();  
10.     public static Set<Integer>set;  
11.     public static void main(String[] args) throws IOException {  
12.         BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));  
13.         int n = Integer.parseInt(cin.readLine());  
14.         String s[] = cin.readLine().split(" ");  
15.         for(int i = 0;i < n;++ i){  
16.             int v = Integer.parseInt(s[i]);  
17.             if(map.containsKey(v)){  
18.                 int cnt = map.get(v);  
19.                 map.put(v, ++ cnt);  
20.             }else{  
21.                 map.put(v, 1);  
22.             }  
23.         }  
24.         set = map.keySet();  
25.         int w = 0;  
26.         while(map.size() != 1 || getcnt() > 1){  
27.             int v1 = setv();  
28.             int v2 = setv();  
29.             int v = v1 + v2;  
30.             w += v;  
31.             if(map.containsKey(v)){  
32.                 int cnt = map.get(v);  
33.                 map.put(v, ++ cnt);  
34.             }else{  
35.                 map.put(v, 1);  
36.             }  
37.         }  
38.         System.out.println(w);  
39.     }  
40.     private static int getcnt() {  
41.         int key = getkey();  
42.         return map.get(key);  
43.     }  
44.     private static int getkey() {  
45.         Iterator<Integer>it = set.iterator();  
46.         while(it.hasNext()){  
47.             return it.next();  
48.         }  
49.         return 0;  
50.     }  
51.     private static int setv() {  
52.         int key = getkey();  
53.         int cnt = map.get(key);  
54.         if(cnt > 1){  
55.             map.put(key, -- cnt);  
56.         }else{  
57.             map.remove(key);  
58.             set.remove(key);  
59.         }  
60.         return key;  
61.     }  
62. }