「NOIP 2004」 合并果子

题目地址

描述

在一个果园里,多多按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过$n-1$次合并之后,就只剩下一堆了,多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
多多在合并果子时要尽可能地节省体力。假定每个果子重量都为$1$,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。
$1 \leq n \leq 10000$

分析

其实是一道哈夫曼树的裸题 QAQ
我们仔细分析冗长的题面后发现,题目其实就是让我们最小化这个式子 $\sum_{i = 1}^{n}w_{i}l_{i}$ 的值,我们可以进行如下的操作:

  • 我们可以用优先队列维护一个小根堆,先将所有的叶子结点放入小根堆。
  • 当堆中元素个数大于 $1$ 时,每次取出堆中两个最小元素,它们同为一个结点的左右儿子,且它们的父亲结点(非叶结点)的权值为两个元素之和。
  • 将两个叶子结点的父亲结点(非叶结点)的权值放回堆中。
  • 循环往复,直至堆中元素个数小于等于 $1$。

时间复杂度为 $\Theta(n)$

代码

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
//  NOIP 2004 合并果子
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved;
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 10000 + 3;
const int INF = 0x3f3f3f3f;
int n;
priority_queue< int, vector<int>, greater<int> > q;
int ans;

int main()
{
n = readIn();
while (!q.empty()) q.pop();
for (int i = 0; i < n; ++i) {
int num = readIn();
q.push(num);
}
ans = 0;
while (q.size() > 1) {
int a = q.top(); q.pop();
int b = q.top(); q.pop();
ans += (a + b);
q.push(a + b);
}
printf("%d\n", ans);
return 0;
}
Partager