题意：分割木板每次切断时，需要的代价是这块木板的长度。求最小代价(哈夫曼树)
题解：每次找出最短的木板L1和次短的木板L2，意味着他们是从一块长度为（ L1+L2 ）木板上切割下来的，然后把（ L1+L2 ）这块板放进数列把L1和L2从数列中删掉，数列长度减一，依次循环。
注意：当最小的板为当前数列的最后一块，就应该把（ L1+L2 ）放在L2的位置，因为每做一次数列长度就要减一。
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cctype> 5 #include <cmath> 6 #include <time.h> 7 #include <string> 8 #include <map> 9 #include <stack> 10 #include <set> 11 #include <queue> 12 #include <vector> 13 #include <algorithm> 14 #include <iostream> 15 using namespace std; 16 typedef long long ll; 17 typedef pair<int,int> P; 18 #define PI acos( -1.0 ) 19 const double E = 1e-8; 20 21 const int NO = 20000 + 5; 22 int a[NO]; 23 int n; 24 ll ans = 0; 25 26 void Solve() 27 { 28 while( n > 1 ) 29 { 30 int x = 0, y = 1; 31 if( a[x] > a[y] ) swap( x, y ); 32 for( int i = 2; i < n; ++i ) 33 { 34 if( a[x] > a[i] ) { 35 y = x; 36 x = i; 37 } 38 else if( a[y] > a[i] ) 39 y = i; 40 } 41 int t = a[x] + a[y]; 42 ans += t; 43 if( x == n-1 ) swap( x, y ); 44 a[x] = t; 45 a[y] = a[n-1]; 46 --n; 47 } 48 printf( "%lld", ans ); 49 } 50 51 int main() 52 { 53 scanf( "%d", &n ); 54 for( int i = 0; i < n; ++i ) 55 scanf( "%d", &a[i] ); 56 Solve(); 57 return 0; 58 }