読者です 読者をやめる 読者になる 読者になる

PKU 3253 Fence Repair

Programming Algorithm PKU

3253 -- Fence Repair

なんか理解に少し時間を要したけど簡単な事だった。

  1. 要求された中で最も短い板2つを足して、コストに加算
  2. それらの長さを足して1枚の板とする
  3. その1枚の長い板と、その他の板の中から、また再び最も短い板2つを足して…(以下続く)

なんだろう、文章化すると難しく思えるけど、アリ本にもあるように二分木の一番深い葉が一番短い板になるような二分木を考えるのだから、ある意味で当然の事と言える。

#include <cstdio>
#include <queue>
using namespace std;
int main(){
	int N;
	scanf("%d\n", &N);

	priority_queue<int, vector<int>, greater<int> > pq;
	for(int i = 0; i < N; i++){
		int L;
		scanf("%d", &L);
		pq.push(L);
	}

	long long cnt = 0;
	while(pq.size() > 1){
		int n = pq.top();pq.pop();
		int m = pq.top();pq.pop();
		cnt += n + m;
		pq.push(n + m);
	}

	printf("%lld\n", cnt);
	return 0;
}