Algoogle

Algorithm for Programming Contest

PKU 3253 Fence Repair

Category: PKU Tag: greedy

Fence Repair

問題概要


長さがsum(L)の板をN本のそれぞれの長さがL[i]の板になるように切りたい.
ただし板を長さxとy切断するときにx+yだけコストがかかる.
コストの最小を求めよ.

解法


蟻本にあるとおり, 切断されたものをマージすると考える.
短いものからマージしたほうがコストが小さくなるのでpriority_queueに板を突っ込んでいき, 短いものを取り出してマージするのを繰り返せばいい.

コード


(3253.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <queue>
#include <cstdio>

using namespace std;
#define int long long

int N, L;
signed main(){
    scanf("%lld", &N);
    priority_queue<int> que;
    for(int i = 0; i < N; i++){
        scanf("%lld", &L);
        que.push(-L);
    }
    int ans = 0;
    while(que.size() > 1){
        int l = -que.top(); que.pop();
        l -= que.top(); que.pop();
        ans += l;
        que.push(-l);
    }
    printf("%lld\n", ans);
    return 0;
}

Comments