[Java] CPE 練習 Add All

這是學校程式大會考, 要用線上程試比賽的方式舉行,
學弟問了一題, 講一講解法就出來了,
雖然網站表明要用C/C++, 
但是最近在練習Java, 就用Java寫了.


Problem F Add All 
Input: standard input 
Output: standard output 

Yup!! The problem name reflects your task; just add a set of numbers. But you may feel yourselves condescended, to write a C/C++ program just to add a set of numbers. Such a problem will simply question your erudition. So, let’s add some flavor of ingenuity to it.

Addition operation requires cost now, and the cost is the summation of those two to be added. So, to add 1 and 10, you need a cost of 11. If you want to add 1, 2 and 3. There are several ways – 

1 + 2 = 3, cost = 3 
3 + 3 = 6, cost = 6 
Total = 9 

1 + 3 = 4, cost = 4 
 2 + 4 = 6, cost = 6 
Total = 10 

2 + 3 = 5, cost = 5 
1 + 5 = 6, cost = 6 
Total = 11 

I hope you have understood already your mission, to add a set of integers so that the cost is minimal. 

Input
Each test case will start with a positive number, N (2 ≤ N ≤ 5000) followed by N positive integers (all are less than 100000). Input is terminated by a case where the value of N is zero. This case should not be processed. 

Output 
For each case print the minimum total cost of addition in a single line. 

Sample Input
3
1 2 3 
4
1 2 3 4 
Output for Sample Input 
9
19
-------------------------------------------------------------------------------- 
Problem setter: Md. Kamruzzaman, EPS


也就是計算成本問題
以1 2 3 4 5舉例, 先計算1 + 2 = 3 這個3就是成本,
在來 成本3繼續往上加3, 3 + 3 = 6 這個6就是成本,
6在往上加, 但是 6 比接下來得4還要來得小, 所以不能這樣加, (題目要計算最小成本)
所以我用的方法是, 因為每次加完成本之後, 成本也變成了加法運算的一員,
所以計算完成本之後, 就在做一次排列, 排列完之後就不會在出現前兩項相加, 
小於後一項的狀況了.

import java.util.*;

public class Add_all_cost{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
               
        int tag_array[] = new int[5000] ; //最多會有5K個測資, 故配至5K的陣列, 都給0
        for(int i = 0; i < 5000 ; i++)
            tag_array[i] = 0;
       
        int count = 0;   //雖然題目是預現給測資個數, 但是覺得煩, 就自己輸入, 最後0結尾
        for(int i = 0; i < 5000 ; i++){
            int a = sc.nextInt();
            if(a != 0){
                count ++;
                tag_array[i] = a;
            }else{
                i+=5000;
            }
        }
 只是用來判斷自己的程式有沒有問題的顯是霸了-------------------------------------------------------------------------------------------------------------       
        System.out.println("Count: "+ count + "\n");  

            for(int l = 0 ; l < count ; l++)
                System.out.print("(" + l + ") " + tag_array[l]+" ");
            System.out.println();   
-------------------------------------------------------------------------------------------------------------          
            for(int j = 0; j < count ; j++){  //開始運算, 因為n個資料只會有n-1次運算, 所以用<
                for(int k = 1 ; k < count ; k++){  //每次運算前就先排列, 雖然沒效率 = =
                    if(tag_array[k-1] > tag_array[k]){
                        int tmp = tag_array[k];
                        tag_array[k] = tag_array[k-1];
                        tag_array[k-1] = tmp;
                    }
                }
            }
           
            int sum = 0, cost = 0;
            for(int i = 0; i < count-1 ; i++){  //其實上面那個是垃圾啦, 因為這裡也排了一次
                for(int j = i; j < count ; j++){
                    for(int k = i+1 ; k < count ; k++){
                        if(tag_array[k-1] > tag_array[k]){
                            int tmp = tag_array[k];
                            tag_array[k] = tag_array[k-1];
                            tag_array[k-1] = tmp;
                        }
                    }
                }
            System.out.print(" Cost: "+ cost+" ");
            for(int l = 0 ; l < count ; l++)
                System.out.print("(" + l + ") " + tag_array[l]);
            System.out.println();
               
                sum = tag_array[i] + tag_array[i+1];  //把每次兩項相加的成本變成i+1項                           tag_array[i+1] = sum;  //因為每次都是i 開始
                cost += sum;  //算成本
            }
           
    System.out.println("Cost: "+ cost);
    }
}


----------------------------------

其他測資

5  Cost: 127
2 3 4 98 1

5 Cost: 745
11 23 65 89 236

10 Cost: 455
1 2 32 41 52 51 4 3 2 1

50 Cost: 19566
9 8 7 6 5 25 85 66 32 159
96 8 7 633 5 25 85 66 32 159
932 81 7 62 5 25 85 66 32 159
9 8 7 61 5 25 85 62 32 159
9 832 7 6 5 25 85 66 32 159

100 Cost: 394282
123 32 56 85 96 456 12346 55 23 1 2 3 85 1598 98
123 32 56 85 96 456 12374 55 23 1 2 3 85 1598 56
123 32 56 85 96 456 12234 55 23 1 2 3 85 1598 23
123 32 56 85 96 456 12334 55 23 1 2 3 85 1598 17
123 32 56 85 96 456 12934 55 23 1 2 3 85 1598 11
123 32 56 85 96 456 12346 55 23 1 2 3 85 1598 98
123 32 56 85 96 456 12346 55 23 1
0