洛谷P1090 [NOIP2004 提高组] 合并果子

题目链接

P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

目录

题目链接

题目描述

输入格式 

输出格式 

代码

题目描述

 在一片果园中，多多已经将所有的果子采摘完毕，并将它们按照种类分成了不同的堆。现在，多多计划将这些果子合并成一堆。

每次合并，多多可以选择任意两堆果子合并，合并时所消耗的体力等于这两堆果子的重量之和。经过 n-1 次合并后，所有的果子将合并成一堆。因此，多多在合并果子过程中总共消耗的体力是每次合并所耗体力的总和。

由于后续还需要将这些果子搬运回家，多多希望在合并果子时尽可能节省体力。假设每个果子的重量都是 1，已知果子的种类数和每种果子的数量，你的任务是设计一个合并方案，使得多多消耗的体力最少，并输出这个最小的体力耗费值。

例如，如果有 3 种果子，数量分别为 1、2、9。可以先合并 1 和 2 这两堆，新堆的数量为 3，消耗体力为 3。然后将新堆与原来的第三堆合并，得到新堆数量为 12，消耗体力为 12。因此，多多总共消耗的体力为 3 + 12 = 15。可以证明 15 是最小的体力耗费值。

输入格式 

共两行。 第一行是一个整数 n（1≤n≤10000），表示果子的种类数。

第二行包含 n 个整数，用空格分隔，第 i 个整数 ai（1≤ai≤20000）表示第 i 种果子的数量。

输出格式 

一个整数，即最小的体力耗费值。输入数据保证这个值小于 2^31。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long  
#define ull unsigned long long
priority_queue<int,vector<int>,greater<int> >p;
void solve() {
	int n,m;
	cin>>n;
	for(int i=0;i<=n-1;i++)
	{
		cin>>m;
		p.push(m);
	}
	long long int sum=0;
	int i=1;
	while(1)
	{
		if(p.size()==1)
        {
            cout<<sum;
            return;
        }
        int num1=p.top();
        p.pop();
        int num2=p.top();
        p.pop();
        p.push(num1+num2);
        sum+=(num1+num2);
	}
 
} 

signed main() {

    ll t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}