Algoogle

Algorithm for Programming Contest

AOJ 2409 Power

Category: AOJ Tag: greedy

Power

問題概要


解法


1番の部屋から埋めていく.
1番の部屋をカバーできる人の中で一番奥の部屋までカバーできる人は選ぶ.
その部屋の次の部屋をカバーできる人のなかで一番奥の部屋まで…
というのを繰り返す. この操作はO(M)なので余裕.
途中で条件を満たせなかったらImpossible

コード


(2409.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
#include <bits/stdc++.h>

#define rep(i,a) for(int i = 0;i < (a); i++)
#define all(u) (u).begin(),(u).end()
using namespace std;
typedef pair<int,int> pii;

int N, M;
vector<pii> inter;

int main(){
    cin >> N >> M;
    inter.resize(M);
    rep(i,M) cin >> inter[i].first >> inter[i].second;
    sort(all(inter));
    int right = 0, cur = 0;
    int cnt = 0;
    bool used[128] = {false};
    while(true){
        if(right == N) {
            cout << cnt << endl;
            return 0;
        }

        int use = -1;
        while(cur < inter.size() && inter[cur].first <= right + 1){
            if(use < inter[cur].second) use = inter[cur].second;
            cur++;
        }
        if(use == -1) break;
        right = use;
        cnt++;
    }
    cout << "Impossible\n";
    return 0;
}

Comments