A5703.简单的合并果子 题解

前言（废话）

好好好，又抄 NOIP 题是吧。

这个题我有两种解法

思路

挺像哈夫曼的。

方法 1

使用 STL 堆，每次弹出都会弹出两个最小的数，计算过后放回去即可。时间复杂度 $O(n \log n)$。

方法 2

我们回归问题的本质，我们还是要选取最小的两堆果子，最清真、最自然的方式显然是排序了吧。先排序，选取最小的两堆果子，然后合并，插入。但是插入的效率太低了，我们想要优化。

我们可以把这些需要插入的点用一个队列存储起来，首先这些需要插入的点肯定会越来越大 显然 ， 这相当于延迟插入。当我们目标插入点就是我们当前最小的那一堆的时候，我们就把他插入进来。

以上是精神，代码写出来大概就是，桶排，建立两个队列，排序结果放进第一个当中，合并结果放在第二个当中，每次选从两个队列队头选取比较小的合并。

——摘自洛谷《题解 P6038 【合并果子 加强版】》

时间复杂度 $O(n)$。

代码

方法 1

记住要设置，不要用初始的排序方法。

可以通过非常简单的 此题。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main(){
	int n,ans=0;
	priority_queue<int,vector<int>,greater<int>> q;
	cin >> n;
	for (int i=0;i<n;++i){
		int t;
		cin >> t;
		q.push(t);
	}
	while (q.size()>1){
		int a=q.top();
		q.pop();
		int b=q.top();
		q.pop();
		ans+=a+b;
		q.push(a+b);
	}
	cout<<ans<<endl;
	return 0;
}

方法 2

同样使用 STL 堆。

可以通过数据量巨大的 此题。

#include <iostream>
#include <queue>
using namespace std;
inline long long read(){char ch=getchar(); long long f=1; while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
    long long x=0; while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}
int main(){
	int n=read();
	long long ans=0;
	vector<int> tot(1e5+5,0);
	queue<long long> q1,q2;
	int mx=-1;
    for (int i=1;i<=n;++i){
    	int t=read();
    	++tot[t];
    	mx=max(mx,t);
	}
    for (int i=1;i<=mx;++i){
    	for (int j=0;j<tot[i];++j){
    		q1.emplace(i);
		}
	}
    for (int i=1;i<n;++i){
        long long x,y;
        if (q2.empty() || (!q1.empty() && q1.front()<q2.front())){
        	x=q1.front();
			q1.pop();
		}else{
			x=q2.front();
			q2.pop();
		}
        if (q2.empty() || (!q1.empty() && q1.front()<q2.front())){
        	y=q1.front();
			q1.pop();
		}else{
        	y=q2.front();
			q2.pop();
		}
        ans+=x+y;
		q2.emplace(x+y);
    }
    printf("%lld",ans);
    return 0;
}