本文共 613 字，大约阅读时间需要 2 分钟。

合并果子 / Fence Repair G

题目链接： /

题目大意

有一堆东西，每次你可以选两个东西，用它们大小的和的代价，把它们合并，得到一个它们大小和的东西。

思路

我们考虑贪心，让每次合并的费用都尽可能小。

自然想到可以每次选已有石头中最小的两个合并。

然后可以用堆维护，然后就可以了。

代码

#include
   
    #include
    
     #define ll long longusing namespace std;int n;priority_queue 
     
      , greater
      
        > q;ll ans, x, y;int main() {   	scanf("%d", &n);	for (int i = 1; i <= n; i++) {   		scanf("%lld", &x);		q.push(x);	}		while (!q.empty()) {   		x = q.top();		q.pop();		y = q.top();		q.pop();				ans += x + y;//代价		if (q.empty()) {   //只剩一个			break;		}		q.push(x + y);//得到新的东西	}		printf("%lld", ans);		return 0;}
      
     
    
   

转载地址：http://mhvh.baihongyu.com/