2437:Muddy roads

PKU

keyword

区間　Greedy　C++

概要

[0..10^9]の互いに素な区間がN(<10^4)個与えられる。これを幅Lの区間でカバーしたい。必要な区間の最小値を求める問題。
左から貪欲に置いていく。割り算とか掛け算で多少計算を省く必要がある。計算量O(N)。

int N, L;
pair<int,int> ranges[10009];

int solve(){
    int ans = 0, cur = -(1<<29);
    for(int i=0; i<N; i++){
        if(cur >= ranges[i].second){
            continue;
        }
        if(cur >= ranges[i].first)
            ranges[i].first = cur;
        int a = ranges[i].second - ranges[i].first;
        a = (a + L - 1)/L;
        ans += a;
        cur = ranges[i].first + a * L;
    }
    return ans;
}