[NOIP2004 提高组] 合并果子-STL容器优先队列priority_queue

[NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

题目描述

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

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

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

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

提示

对于 $30\%$ 的数据，保证有 $n\le 1000$：

对于 $50\%$ 的数据，保证有 $n\le 5000$；

对于全部的数据，保证有 $n\le 10000$。
题意

要使体力耗费值最小，即每次合并现有的果子中最小的两堆，把每次的体力值加起来就是最终值（哈夫曼编码）

以果子 5 10 13 14举例：

解题过程

思路

• 第一种想到的就是最简单的就是数组储存，每次合并两个数据，然后将合并后的果子数插入到数组，重新排序，看下n,合并一次排序一次，时间复杂度O(n^ 2* logn) 也还可以，n再大一点就G

• 第二种就是升序排列每次都取前两个，并且将值插进去排序，优先队列-小顶堆能解决这个问题。

  时间复杂度分析：

  1. 初始化堆： 将 n 个元素插入到小顶堆中的时间复杂度是 O(n log n)。因为每次插入堆的时间复杂度是 O(log n)，总共插入 n 次，所以时间复杂度是 O(n log n)。

  2. 合并过程： 在每次合并中，都会执行以下操作：

     • 从堆中弹出两个元素（每次操作的时间复杂度是 O(log n)），
     • 将它们合并后的结果再次插入堆中（插入的时间复杂度也是 O(log n)）。

     由于每次从堆中弹出和插入的操作时间复杂度是 O(log n)，而合并的次数总共是 n-1 次（因为最终堆中剩下一个元素），因此合并过程的总时间复杂度是 O(n log n)。

​ 算法非常高效，适用于大多数需要进行合并或优先级操作的问题！

数据约束

n≤10000

参考代码-队列

#include <bits/stdc++.h>
using namespace std;
//定义一个小顶堆
int main() {
	priority_queue< int ,vector<int>, greater<int> > pq ; 
//	 set<int, greater<int> > s;  
	int n,k;
	long long ans = 0;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>k;
		pq.push(k);
	}
	int a,b; 
	while(!pq.empty()){
		a = pq.top();
		pq.pop();
		if(!pq.empty()) { //不是最后一个 
			b = pq.top();
//			cout<<" b:"<<b;
			pq.pop();
			ans += (a+b);
//			cout<<ans<<" // "<<a+b<<endl;
			pq.push(a+b);
		}else{
			//只有一个的情况
			cout<<ans;
			break;	
		}
		
	}

}

参考代码-数组

#include<bits/stdc++.h>
using namespace std;
long long a[10001]={0};
int main(){
	
	long n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int num=0;
	sort(a,a+n);
	for(int i=0;i<n-1;i+=1){
		a[i+1]=a[i]+a[i+1];
		num+=a[i+1];
		sort(a+i+1,a+n);
	} 
	cout<<num;
	return 0;
}

优先队列知识点

在 C++ 中，STL（标准模板库）提供了 priority_queue 类，用于实现优先队列。优先队列是一种特殊的队列，其中元素根据其优先级进行排序，优先级高的元素最先出队。

1. 优先队列概述

STL 中的 priority_queue 默认是一个最大堆（max-heap），即堆顶元素具有最大的优先级。如果你想要实现最小堆（min-heap），需要显式地指定比较函数。

• 最大堆：堆顶的元素优先出队。

• 最小堆：堆顶的元素优先出队。

  

2. priority_queue 的基本操作

priority_queue 提供的基本操作有：

• push()：将元素添加到队列中。
• pop()：移除队列中优先级最高（堆顶）的元素。
• top()：返回队列中优先级最高的元素（但不移除它）。
• empty()：检查队列是否为空。
• size()：返回队列中的元素数量。

3. 默认的最大堆实现

默认情况下，priority_queue 是一个最大堆，意味着堆顶元素总是队列中的最大元素。

代码示例：最大堆（默认行为）

#include <bits/stdc++.h>
using namespace std;
int main() {
    // 创建一个优先队列（最大堆）
    priority_queue<int> pq;
    // 插入元素
    pq.push(10);
    pq.push(20);
    pq.push(5);
    pq.push(15);
    // 打印并移除堆顶元素
    while (!pq.empty()) {
        cout << pq.top() << " ";  // 输出堆顶元素        20 15 10 5
        pq.pop();  // 移除堆顶元素
    }
    cout <<endl;
    return 0;
}

代码示例：最小堆

priority_queue 的模板参数通常是三个类型：

cppCopy Codepriority_queue<T, Container, Compare>

• T 是队列中存储的元素类型（例如 int）。
• Container 是底层容器类型，默认是 vector<T>。
• Compare 是用于比较元素的函数对象（即比较器），默认是 less<T>，表示最大堆。

#include <bits/stdc++.h>
using namespace std;
int main() {
    // 创建一个优先队列（最小堆）
    priority_queue<int, vector<int>, greater<int>> pq; //必须第二个参数要有底层容器类型
    // 插入元素
    pq.push(10);
    pq.push(20);
    pq.push(5);
    pq.push(15);
    // 打印并移除堆顶元素
    while (!pq.empty()) {
        cout << pq.top() << " ";  // 输出堆顶元素
        pq.pop();  // 移除堆顶元素
    }
    cout <<endl;
    return 0;
}