【贪心】【堆】Gym - 101128C

一些画布，每块有其大小，一开始都是白的，你任意将它们排序，然后一次操作可以选择一段连续的相同颜色的画布，从中任选一个位置，左侧涂上任意一种颜色，右侧涂上另一种。消耗是这一段画布的总的大小。问你要将所有画布着上不同的颜色的最小花费。

从后向前考虑，其实相当于是将一些一开始不同的画布两两合并，代价是两者之和，然后新生成的画布是两者之和，问最小花费。

由于你可以随便排序，所以其实是NOIP合并果子。

#include<cstdio>

#include<queue>

using namespace std;

typedef long long ll;

int T,n;

priority_queue<ll,vector<ll>,greater<ll> >Heap;

int main(){

//	freopen("c.in","r",stdin);

	int x;

	scanf("%d",&T);

	for(;T;--T){

		while(!Heap.empty()){

			Heap.pop();

		}

		ll ans=0;

		scanf("%d",&n);

		for(int i=1;i<=n;++i){

			scanf("%d",&x);

			Heap.push((ll)x);

		}

		while(Heap.size()>1){

			ll A=Heap.top(); Heap.pop();

			ll B=Heap.top(); Heap.pop();

			ans+=(A+B);

			Heap.push(A+B);

		}

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

【贪心】【堆】Gym - 101128C - Canvas Painting

最新文章

热门文章