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. }