POJ 3253 Fence Repair

想法：
　　題目雖然說是砍斷，但其實可以想成一塊一塊拼回來，兩塊兩塊拼成的長度就是收取的費用，這題跟 UVa 10954 Add All 做法一樣，用priority_queue。

	#include <cstdio>
	#include <queue>
	using namespace std;
	typedef long long int llt;
	int main()
	{
	llt N, L;
	while (scanf("%lld", &N) != EOF) {
	priority_queue<llt, vector<llt>, greater<llt> > PQ;
	for (llt i = 0; i < N; ++i) {
	scanf("%lld", &L);
	PQ.push(L);
	}
	llt sum = 0;
	while (PQ.size() > 1) {
	llt tmp = PQ.top();
	PQ.pop();
	tmp += PQ.top();
	PQ.pop();
	sum += tmp;
	PQ.push(tmp);
	}
	printf("%lld\n", sum);
	}
	return 0;
	}

view raw [POJ] 3253 Fence Repair.cpp hosted with ❤ by GitHub