洛谷P1090题解

一、题意简述

有n堆果子，每堆果子都有一个值$a_i$，合并两堆果子需要$a_i$和$a_j$相加的体力，要求n堆果子和并成一堆果子最小花费的体力。

二、求什么

求n堆果子和并成一堆果子最小花费的体力。

三、解题方法

利用堆的pop操作和top操作来解题。

四、Code

#include <bits/stdc++.h>
using namespace std;
int n,s;
priority_queue<int,vector<int>,greater<int> >heap;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		int temp;
		scanf("%d",&temp);
		heap.push(temp);
	}
	int a,b;
	while(heap.size()>=2)
	{
		a=heap.top();
		heap.pop();
		b=heap.top();
		heap.pop();
		s+=a+b;
		heap.push(a+b);
	}
	printf("%d",s);
	return 0;
}

浏览次数: