刷题记录:牛客NC16663[NOIP2004]合并果子

传送门:牛客

题目描述:

    在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有
的果子合成一堆。
    每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果
子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
    因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为
1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，
并输出这个最小的体力耗费值。

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

当年NOIP提高组的一道题,是一道经典的贪心题,难度并不大,洛谷上还有加强版

对于这道题我们需要用到的是C++里面的优先队列当然也可以自己手打优先队列(虽然但是,没必要)

对于一般的优先队列,priority_queuepq,是一个"越小的整数优先级越低的优先队列"

对于另一种"越大的整数优先级越低的优先队列",我们需要加入cmp比较函数(类似于sort)

struct cmp{
	bool operator() (const int a,const int b) const{
		return a>b;
	}
};
priority_queue<int,vector<int>,cmp>pq

并且c++还为我们准备了更加方便的STL写法

priority_queue<int,vector<int>,greater<int> >pq       
注意此处最后的两个大于号之间要留有空格,不然编译器会将其当做  >>  运算符

有了优先队列的前置知识之后我们也就不难写出这道题了

对于每一次的合并,我们发现每一堆对之后的影响都是持久的,也就是越早合并的果堆被用到的次数越多,那么显然的,如果我们需要最优解显然是将每一次合并完的最小两个堆进行再一次的合并即可,对于维护这种 *** 作我们使用优先队列(sort会超时)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
//priority_queue,greater >pq;    简便写法
struct cmp{
	bool operator() (const int a,const int b) const {
		return a>b;
	}
};
//详细写法
priority_queue<int,vector<int>,cmp>pq;
int main() {
	int n;n=read();
	int a;
	for(int i=1;i<=n;i++) {
		a=read();
		pq.push(a);
	}
	int ans=0;
	int fi,se;
	while(pq.size()>1) {
		fi=pq.top();
		pq.pop();
		se=pq.top();
		pq.pop();
		ans+=(fi+se);
		pq.push(fi+se);
	}
	cout<<ans<<endl;
	return 0;
}