洛谷P6033 合并果子 加强版

---

传送门 $\looparrowright$

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 $n−1$ 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 $1$，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有 $3$ 堆果子，数目依次为 $1,2,9$。可以先将 $1$、$2$ 堆合并，新堆数目为 $3$，耗费体力为 $3$。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 $12$，耗费体力为 $12$。所以多多总共耗费体力为 $3+12=15$ 。可以证明 $15$ 为最小的体力耗费值。

输入格式

输入的第一行是一个整数 $n$，代表果子的堆数。
输入的第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 堆果子的个数 $a_i$ 。

输出格式

输出一行一个整数，表示最小耗费的体力值。

输入输出样例

输入 #1

3
1 2 9

输出 #1

15

说明/提示

【数据规模与约定】
本题采用多测试点捆绑测试，共有四个子任务。
Subtask 1（10 points）：$1 \leq n \leq 8$ 。
Subtask 2（20 points）：$1 \leq n \leq 10^3$ 。
Subtask 3（30 points）：$1 \leq n \leq 10^5$ 。
Subtask 4（40 points）：$1 \leq n \leq 10^7$ 。
对于全部的测试点，保证 $1 \leq a_i \leq 10^5$ 。
【提示】
请注意常数因子对程序效率造成的影响。
请使用类型合适的变量来存储本题的结果。
本题输入规模较大，请注意数据读入对程序效率造成的影响。

分析

此题与 $\text{POJ 3253}$ 同源。每次合并只需要取出最小值和次小值。如果用优先队列实现，时间复杂度为 $O(n\log n)$，然而数据规模达到了 $10^7 $，显然会 $\text{TLE}$，因此需要进行算法优化。
每次合并都要取出最小值和次小值，每次取值，有两种选择：选择没有合并过的果子，或者选择已经合并过的一堆果子。我们可以维护两个普通队列 $alone$ 和 $united$，分别装没有合并过的果子和已经合并过的堆。
读入时要将数据从小到大排序，并推入队列 $alone$。由于数据规模较大，且数据域在 $10^5$ 内，可以利用桶排序实现该操作，此时桶排序优于快速排序。完成排序后 $alone$ 中是有序的数据，$united$ 为空。
第一次合并时，我们从 $alone$ 中取出前两个合并，将其推入 $united$ 中。由于合并好的堆会越来越大，最终达到 $\sum\limits_{i=1}^na_i$ ，所以 $united$ 中的数据始终也是有序的（升序）。每次合并只需要比较 $alone$ 和 $united$ 的队头大小，每次从两个队列队头选取比较小的合并；当然，当其中一个队列为空时，只能从另一个队列中取值。
算法的时间复杂度为 $O(n)$ 。

代码

#include<queue>
#include<cstdio>
#include<iostream>
#define N 100002
#define ll long long
using namespace std;
int bucket[N];
int n;
queue<ll>alone,united;
ll ans;
inline ll read()//快读模板
{
	ll X=0; 
	bool flag=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') 
	{
		if(ch=='-') flag=0; 
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') 
	{
		X=(X<<1)+(X<<3)+ch-'0'; 
		ch=getchar();
	}
	if(flag) return X;
	else return ~(X-1);
}
void bucket_sort()//桶排序模板
{
	int i;
	for(i=1;i<N;i++)
	{
		while(bucket[i])
		{
			alone.push(i);
			bucket[i]--;
		}
	}
}
inline ll choose()
{
	//每次取值比较两个队列的对头取最小
	ll minimum;
	if(united.empty())
	{
		minimum=alone.front();
		alone.pop();
	}
	else if(alone.empty())
	{
		minimum=united.front();
		united.pop();
	}
	else if(alone.front()<=united.front())
	{
		minimum=alone.front();
		alone.pop();
	}
	else 
	{
		minimum=united.front();
		united.pop();
	}
	return minimum;
}
int main()
{
	n=read();
	int i;
	for(i=1;i<=n;i++) 
	{
		ll temp=read();
		bucket[temp]++;//计数
	}
	bucket_sort();//桶排序
	for(i=1;i<=n-1;i++)
	{
		ll first_minimum,second_minimum;
		first_minimum=choose();
		second_minimum=choose();
		ans+=first_minimum+second_minimum;//叠加
		united.push(first_minimum+second_minimum);//推入队列
	}
	cout<<ans<<endl;
	return 0;
}