【CSU-1588】解题报告（贪心，水题）

原始题目

1588: 合并果子

  • Time Limit: 1 Sec
  • Memory Limit: 128 Mb
  • Submitted: 1907
  • Solved: 906

Description

现在有\(n\)堆果子，第\(i\)堆有 \(a_i\)个果子。现在要把这些果子合并成一堆，每次合并的代价是两堆果子的总果子数。求合并所有果子的最小代价。 ### Input 第一行包含一个整数\(T(T \le 50)\)，表示数据组数。

每组数据第一行包含一个整数$ n( 2 n 1000 )$ ，表示果子的堆数。

第二行包含\(n\)个正整数$a_i ( a_i 100) $，表示每堆果子的果子数。

Output

每组数据仅一行，表示最小合并代价。

Sample Input

2
4
1 2 3 4
5
3 5 2 1 4

Sample Output

19
33

Hint

Source

国防科学技术大学第十八届银河之光文化节ACM程序设计竞赛初赛

题目大意

如题 # 解题思路 - 贪心，优先队列，每次取顶上两堆果子。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//#include <bits/stdc++.h>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <set>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#define INF 0x3f3f3f3f
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
using namespace std;
const int maxn=1e5+5;
 
typedef long long ll;
ll t,n,a[maxn];
priority_queue<ll, vector<ll>, greater<ll> > pq;


int main(){
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--){
		while(!pq.empty()) pq.pop();
		int n; ll sum=0,sum1,a;
		cin>>n;
		rep(i,0,n){
			cin>>a;
			pq.push(a);
		}
		while(!pq.empty()){
			sum1=pq.top();
			pq.pop();
			sum1+=pq.top();
			pq.pop();
			if(pq.empty()){
//				cout<<"empty"<<sum1<<endl;
				sum+=sum1;break;
			}
			else{
				sum+=sum1;
//				cout<<"get"<<sum1<<endl;
				pq.push(sum1);
			}  
		}
		cout<<sum<<endl;
	}
}

收获与反思

水题