Uva12321 - Gas Stations

題目大意

有一個道路紹面有許多瓦斯站(會給與位置以及覆蓋半徑)，但似乎有些覆蓋部分是重複的，我們需要找出最多可以移掉幾個瓦斯站且不影響覆蓋率(0~L 都有覆蓋)

重點觀念

分析

• 將每個瓦斯站覆蓋的起點與終點存成一個 pair
• 從 0 開始尋找可以覆蓋的最大瓦斯站

程式題目碼

#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    int l, g;
    while (cin >> l >> g, l > 0 && g > 0) {
        pair<int, int> range[g];
        for (int i = 0; i < g; i++) {
            int x, r;
            cin >> x >> r;
            range[i] = make_pair(x - r, x + r);
        }

        sort(range, range + g);

        int covered_len = 0, ans = g;
        int i = 0;
        while (covered_len < l) {
            int temp_len = covered_len;
            for (; i < g && range[i].first <= covered_len; i++) {
                if (range[i].second > temp_len) {
                    temp_len = range[i].second;
                }
            }
            if (temp_len == covered_len) {
                break;
            }

            covered_len = temp_len;
            ans--;
        }

        if (covered_len < l) {
            cout << -1;
        } else {
            cout << ans;
        }

        cout << endl;
    }

    return 0;
}