Algoogle

Algorithm for Programming Contest

PKU 2437 Muddy roads

Category: PKU Tag: greedy

Muddy roads

問題概要


解法


とりあえずmudの位置はソートしておく.
あとは順に板を置いて, 板の末尾を覚えておく.
次のmudの始まりより板の末尾が前だったらmudの始まりからまた順に板を敷き詰める.
そうでないなら板の末尾から敷き詰める.
このやり方では板の末尾のチェックの時に完全にmudを覆っている場合に注意する.

コード


(2437.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
25
26
27
28
29
30
31
32
#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;

typedef pair<int,int> pii;

int N, L;
pii mud[10010];

int main(){
    scanf("%d%d", &N, &L);
    for(int i = 0; i < N; i++){
        int s, t;
        scanf("%d%d", &s, &t);
        mud[i] = pii(s,t);
    }
    sort(mud, mud+N);
    int tail = 0, ans = 0;
    for(int i = 0; i < N; i++){
        if(tail >= mud[i].second) continue;
        tail = max(mud[i].first, tail);
        int res = mud[i].second - tail;
        int num = res / L;
        if(res % L) num++;
        tail += num * L;
        ans += num;
    }
    printf("%d\n", ans);
    return 0;
}

Comments