合并果子(fruit) （其实这题小根堆也可以做的）

// 本题使用堆排序，用小根堆维护 
#include <bits/stdc++.h>
using namespace std;

int n, x, sum, ans;
priority_queue<int,vector<int>,greater<int> > q; //小根堆 

int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> x;
		q.push(x); // 边读入编存 
	}
	// 思路：取出前两个数，合并后重新放入堆 
	while (q.size() > 1) // 在堆里还有1个的情况下均可合并果子 
	{
		sum += q.top();
		q.pop(); //出队 
		sum += q.top();
		q.pop(); // 再次出队		
		ans += sum; // 全部累加 
		q.push(sum);
		sum = 0; // 清空sum 
	}
	cout << ans << endl; // 输出ans即可 
	return 0;
}

题意

求一堆不同重量的果子合在一起最少要耗费多少体力

每次只能合两堆,耗费果子个数的体力

代码

#include<iostream>
#include<queue>
using namespace std;
int n,sum=0;
priority_queue<int>q;//优先队列
int main()
{
    cin>>n;//输入
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;//输入
        q.push(-x);//相反数入队
    }
    int x=0,y=0;
    while(q.size()-1)//要减1,留下最后的结果
    {
        x=-q.top();
        q.pop();
        y=0;
        if(q.size())//判空
        {
            y=-q.top();//获取后面一个
            q.pop();
        }
        sum+=x+y;//求和
        q.push(-(x+y));//入队
    }
    cout<<sum;//输出
    return 0;//完结散花
}

题意

有 $n$ 个数，要把它们合并成一个数。合并第 $i$ 和第 $j$ 个数时要花费 $a_i$ 和 $a_j$ 个力气合并，求最小的力气

其实题目讲的已经够清楚了

思路

要使力气最小，肯定得让合并的两个数尽量小，这样合并出来的数也会小（相比）

说到小是不是就想到了 sort？但 sort 加数组写起来很复杂（不会爆），所以用优先队列

优先队列是大的排前面，所以用相反数来小的排前，最后输出答案输出相反数就行了

代码

#include <bits/stdc++.h>
using namespace std;
priority_queue<int> q;
int sum;
int main(int argc, char **argv){
	int n;
	cin >> n;
	for (int i = 0;i < n;i++){
		int x;
		cin >> x;
		q.push(-x);
	}
	while (1){
		int a = q.top();
		q.pop();
		if (q.empty()){
			break;
		}
		int b = q.top();
		q.pop();
		q.push(a + b);
		sum += a + b;
	}
	cout << -sum;
	return 0;
}

#include<bits/stdc++.h> 
using namespace std;
priority_queue<int>q;
int main(){
	long long n,k=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		q.push(-a);
	}
	while(q.size()>1){
		int x=q.top();
		q.pop();
		int y=q.top();
		q.pop();
		k=k-x-y;
		q.push(x+y);
	}
	cout<<k;
}

// Huffman 编码 

#include <cstdio>
#include <queue>

using namespace std;

priority_queue<int, vector<int>, greater<int> > pq;	// 小根堆，小的在前面 
int n, a, x, y, ans = 0;

int main()
{
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a);
		pq.push(a);
	}
	
	while (pq.size() > 1)	// 大于一堆时 
	{
		x = pq.top(); pq.pop();	// 取最小值 ，出队 
		y = pq.top(); pq.pop();	// 取最小值 ，出队 
		
		ans += x + y;			// 计算贡献 
		pq.push(x + y);			// 放回 pq 
	}
	
	printf("%d", ans);
	
	return 0;
}

题意

求n个正整数轮次求和中所出现的数（除了原数与结果）的和。

死路

首先我的想法就是用一个数组，一直sort，n逐渐-1，直至n=1。

statement

死路、歹马之所以会出现，是为了告诉同学，如何分析一个思路是正确还是错误的。和我们平时做题有专题的提示不同，比赛要用哪个思路是要自己想的。比赛越来越难，思路不会再写在题目上面了，一道题可能有好多种可能做出来的死路，但只有一种是思路。如果每一种都写完歹马再发现问题，就会耗费很多时间。所以我们一定要学会迅速发现死路与歹马的问题，及时更换思路。

问题

从时间复杂度分析，sort的时间复杂度是$log_2n$，所以这个死路去做，级别会到达$nlog_n$级别，大概是六位数左右，不会爆。

从写代码分析，这样写的话，n=2，n=1这样的边界很难处理，所以我倾向于用以下方法

思路

这需要用一个叫优先队列的容器。

现在就只需要把前两个元素pop掉，然后加和，再push它们的和就可以了。

当你pop掉一个就空了的话，就说明只剩下一堆了。

#include<iostream>
#include<queue>
using namespace std;
int main(){
	priority_queue<int> q;
	int n;
	cin>>n;
	while(n--){
		int a;
		cin>>a;
		q.push(-a);
	}
	int sum=0;
	while(true){
		int a=-q.top();
		q.pop();
		if(q.empty())
			break;
		int b=-q.top();
		q.pop();
		sum+=a+b;
		q.push(-a-b);
	}
	cout<<sum;
}