2.1 截木板    【贪心法（Huffman 编码）】

截断一块木板时，开销为此木板的长度。现在将一根很长的木板截成 N 块，第 i 块长度为 L_i 。求最小开销。

Limits: (1 <= N <= 20000, 0 <= L_i <= 50000)

样例： 输入： N = 3,  L = {8, 5, 8}      输出： 34 (21 + 13)

思路：方法1. 根据 N 块木板长度，构建 Huffman 树。 时间复杂度：O(N²)

typedef long long ll;void solve(int L[], int N) {	ll cost = 0;	while (N > 1) {		int firMin = 0, secMin = 1;		if (L[firMin] > L[secMin]) swap(L[firMin], L[secMin]);		for (int i = 2; i < N; ++i) {			if (L[i] < L[firMin]) {				secMin = firMin;				firMin = i;			} else if (L[i] < L[secMin]) {				secMin = i;			}		}		int tmp = L[firMin] + L[secMin];		cost += tmp;		if(firMin == N-1) L[secMin] = tmp;		else {			L[firMin] = tmp;			L[secMin] = L[N-1];		}		N--;	}	cout << cost << endl;	/*printf("%lld\n", cost);*/}

 方法2：优先级队列 (基于堆实现)。 时间复杂度: O(NlogN)

typedef long long ll;void solve(int L[], int N) {	ll cost = 0;	/***  实现一个从小到大取值的优先级队列  ***/	priority_queue
     

, greater

> que; for (int i = 0; i < N; i++) { que.push(L[i]); } while (que.size() > 1) { int L1 = que.top(); que.pop(); int L2 = que.top(); que.pop(); cost += L1 + L2; que.push(L1 + L2); } cout << cost << endl; /*printf("%lld\n", cost);*/}