#12921: 這題跟d221是同一個題目


tntchn (tntchn)

School : 國立成功大學
ID : 40564
IP address : [36.238.8.3]
Last Login :
2018-01-23 23:41:28
b606. Add All -- 2016 NEHS校內上機考 | From: [140.116.109.140] | Post Date : 2017-11-05 23:28

不過那邊測資比較強
在此附上在這邊跟那邊都AC的code
有興趣的可以去那邊挑戰

#include <iostream>
#include <list>
#include <algorithm>
using namespace std; 

int main () {
    int n;
    while (cin >> n && n != 0) {
        list<int> huffman;
        {
            int a[n];
            for (int i=0; i<n; i++) cin >> a[i];
            sort(a,a+n);
            huffman.assign(a,a+n);
        }
        
        long long cost = 0;
        while (huffman.size() > 1) {
            long long sum = 0;
            auto it = huffman.begin();
            for (int i=0; i<2; i++) {
                sum += *it;
                it++;
            }
            cost += sum;
            while (sum > *it && it != huffman.end()) it++;
            huffman.insert(it,sum);
            huffman.pop_front();
            huffman.pop_front();
        }
        
        cout << cost << endl;
    }
    
    return 0;
}
 
ZeroJudge Forum