poj 3253 Fence Repair 贪心

缘起

日常水题

poj 3253 Fence Repair

分析

题意

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
需要n块木板，长度依次是L1,...,Ln, 手头上有一块长L1+...+Ln的木板, 将一块长L的木板锯成x,y两截的耗费是x+y. 问
为了达到目标，最小耗费是多少?

【输入】
第一行是n（1<=n<=20000）
2...n+1行是 L1,...,Ln （0<=Li<=50000）

【输出】
最小耗费

【样例输入】
3
8
5
8

【样例输出】
34

【限制】
Time Limit: 2000MS
Memory Limit: 65536K

将原先完整的木板视作二叉树的根节点, 然后每次切割分裂成2个子节点. 代价是两个子节点的长度和. 则不断分下去, 这棵二叉树的叶子节点就是需要的木板L1,…,Ln. 总代价其实就是Huffman树建树过程（$\Sigma$叶子的深度*叶子的权）. 也就是我们需要使用 L1,…Ln 建立（带权）Huffman树.

而建立Huffman树的算法是贪心，而且是我们一直都熟知的——

1
2
S={L1,..,Ln} 从中挑出权最小的2个L_min1和L_min2并且从S中删掉他们, 然后答案增加L_min1+L_min2, 然后将此和放
进S, 则|S|减少1，如此往复,直至|S|=1(剩下的这个就是Huffman树的根节点), 则此时得到的答案就是题解

注意，因为每次要选出最小的两个，所以自然使用优先队列——即Huffman算法可以使用优先队列加速. 算法复杂度是O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//#include "stdafx.h"

#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
//#define LOCAL

typedef long long LL; // 不用 LL 会wa

priority_queue<int,vector<int>, greater<int> > pq;

int main() 
{

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	LL ans = 0;
	int n,t;
	scanf("%d", &n);
	while(n--)
	{
		scanf("%d", &t);
		if (t) pq.push(t);
	}
	while(pq.size()>1)
	{
		int a = pq.top();
		pq.pop();
		int b = pq.top();
		pq.pop();
		ans+=a+b;
		pq.push(a+b);
	}
	printf("%lld\n", ans);
	return 0;
}

ac情况

20749832 yfsyfs 3253 Accepted 728K 32MS G++ 515B 2019-08-16 11:43:02