Algoogle

Algorithm for Programming Contest

PKU 2376 Cleaning Shifts

Category: PKU Tag: greedy

Cleaning Shifts

問題概要


N匹の牛に対して仕事できる時間の区間が与えられるので, 時間Tまでの間すべてをカバーする最小の牛の数を求める.

解法


greedyにやればいい.
現在カバーしてる範囲から仕事を始められる牛のうち, 一番遅くまで仕事する牛を選べば明らかに最適.
開始時刻でソートしておく.

コード


(2376.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
33
34
35
36
37
38
#include <algorithm>
#include <cstdio>
#include <map>

using namespace std;

typedef pair<int,int> pii;

int N, T;
pii sect[25010];

int main(){
    scanf("%d%d", &N, &T);
    for(int i = 0; i < N; i++){
        int a, b; scanf("%d%d", &a, &b);
        sect[i] = pii(a-1,b);
    }
    sort(sect, sect+N);
    int ans = 0;
    int r = 0, pos = 0;
    while(r < T){
        int mr = 0;
        while(pos < N && sect[pos].first <= r)
            mr = max(mr, sect[pos++].second);
        ans++;
        if(pos == N){
            if(mr < T) ans = -1;
            break;
        }
        if(mr == 0){
            ans = -1;
            break;
        }
        r = mr;
    }
    printf("%d\n", ans);
    return 0;
}

Comments