洛谷P1090 合并果子

发表于 | 更新于: | 分类于 ， | | 阅读数
字数统计: 1k | 阅读时长 ≈ 4

Description

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有3种果子，数目依次为1，2，9。可以先将1 、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12 ，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

Input

共两行。
第一行是一个整数$n(1\leq n\leq10000)$，表示果子的种类数。

第二行包含n个整数，用空格分隔，第i个整数$a_i(1\leq a_i\leq20000)$是第i种果子的数目。

Output

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于$2^{31}$。

Sample Input

1
2
3 
1 2 9

Sample Output

1
15

Analysis

看似是道水题，贪心每次选最小的两组即可，但是一写发现每次选完都要排序，肯定会T。于是想到用优先队列维护一下，刚好我也不会优先队列，就写个博客吧23333.

顺便贴个优先队列的相关知识，转自OI Wiki。

priority_queue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <queue>  // std::priority_queue
// 本文里的所有优先队列都会加上命名空间
// 如果不想加命名空间，需要使用：using std::priority_queue;
// 不推荐直接使用 using namespace std;
std::priority_queue<T, Container, Compare>
    /*
     * T: 储存的元素类型
     * Container:
     * 储存的容器类型，且要求满足顺序容器的要求、具有随机访问迭代器的要求 且支持
     * front() / push_back() / pop_back() 三个函数， 标准容器中 std::vector /
     * std::deque 满足这些要求。 Compare: 默认为严格的弱序比较类型
     * priority_queue 是按照元素优先级大的在堆顶，根据 operator <
     * 的定义，默认是大根堆， 我们可以利用
     * greater<T>（若支持），或者自定义类的小于号重载实现排序。
     * 注意：只支持小于号重载而不支持其他比较符号的重载。
     */
    // 构造方式 ：
    std::priority_queue<int>;
std::priority_queue<int, vector<int>>
    // C++11前，请使用 vector<int> >，空格不可省略
    std::priority_queue<int, deque<int>, greater<int>>
    // 注意：不可跳过容器参数直接传入比较类
成员函数
  1. top() : 访问栈顶元素 常数复杂度
  2. empty() : 检查底层的容器是否为空 常数复杂度
  3. size() : 返回底层容器的元素数量 常数复杂度
  4. push() : 插入元素，并对底层容器排序 最坏$\Theta(n)$均摊$\Theta(log(n))$
  5. pop() : 删除第一个元素 最坏$\Theta(log(n))$

由于 std::priority_queue 原生不支持 modify() / join() / erase() 故不做讲解。

Code

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
39
#include <iostream>
#include <algorithm>
#include <functional>
#include <queue>
#include <vector>
using namespace std;

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

int main()
{
	while (cin >> n)
	{
		int sum = 0;
		for (int i = 1; i <= n; i++)
		{
			cin >> a;
			pq.push(a);
		}
		if (n == 1)
			cout << a << endl;
		else
		{
			for (int i = 1; i < n; i++)
			{
				int l = pq.top();
				pq.pop();
				int r = pq.top();
				pq.pop();
				sum += l + r;
				pq.push(l + r);
			}
			cout << sum << endl;
		}
	}
	return 0;
}