/* 解析见挑战P48-49 法一:递归--复杂度(O(n^2)) */ #include <iostream> typedef long long ll; const int MAX_N = 2e4 + 10; int N, L[MAX_N]; using namespace std; void show() { for (int i = 0; i < N; i++) cout << L[i] << " "; cout << endl; } void solve() { ll ans = 0; // 直到计算模板为1块为止 while ( N > 1 ) { // 求出最短的板的下标mii1,和次短的板的下标mii2 int mii1 = 0, mii2 = 1; if ( L[mii1] > L[mii2] ) swap(mii1, mii2); for ( int i = 2; i < N; i++ ) { if ( L[i] < L[mii1] ) { mii2 = mii1; mii1 = i; } else if ( L[i] < L[mii2] ) { mii2 = i; } } // show(); // 将两块板拼合 int t = L[mii1] + L[mii2]; ans += t; // cout << L[mii1] << " " << L[mii2] << endl; // cout << "ans = " << ans << endl; if (mii1 == N - 1) swap(mii1, mii2); L[mii1] = t; L[mii2] = L[N - 1]; // cout << "after changed: " << L[mii1] << " " << L[mii2] << endl; // cout << "mii1 = " << mii1 << " mii2 = " << mii2 << endl; // show(); N--; } cout << ans << endl; } int main() { cin >> N; for ( int i = 0; i < N; i++ ) { cin >> L[i]; } solve( ); return 0; }
//法二:见挑战 P77 //改进:使用优先队列 复杂度O(nlogn) #include <iostream> #include <queue> typedef long long ll; const int MAX_N = 2e4 + 10; int N, L[MAX_N]; using namespace std; typedef long long ll; typedef priority_queue<int, vector<int>, greater<int> > QUEUE; //void test(QUEUE a) //{ // while (a.size()) // { // cout << a.top() << endl; // a.pop(); // } //} void solve() { ll ans = 0; // 声明一个从小到大取出数值的优先队列 QUEUE que; for (int i = 0; i < N; i++) que.push(L[i]); // test(que); // 循环到只剩下一块木板为止 while (que.size() > 1) { // 取出最短的木板和次短的木板 int l1, l2; l1 = que.top(); que.pop(); l2 = que.top(); que.pop(); // 把两块木板合并 ans += l1 + l2; que.push(l1 + l2); // test(que); } cout << ans << endl; } int main() { cin >> N; for ( int i = 0; i < N; i++ ) { cin >> L[i]; } solve( ); return 0; }