UVa12321 - Gas Stations(設計解題、貪心)

題目大意

在一條主要幹道上，有許多加油站，其中每一個加油站都會影響主要幹道上的某個區段，用 \([x+r, x-r])\) 表示，x 是道路位置、r 是影像長度，其中幹道上的每一個點都有被加油站區斷給覆蓋到，現在加油站公司想要把一些加油站刪除，前提是幹道上的每一個點都還是必須有一個加油站覆蓋到。
請問總共可以刪掉幾個加油站？
如果不行，輸出 -1

題目連結

重點觀念

• 英文閱讀
• 整個程式碼的架構

分析

其實這個問題並不難，但要花點心思處理。

• 我們主要是要讓整個幹道的每個點被覆蓋到
  • 因此我們需要先讓所有的加油站影響區段都記錄下來，我們用 pair 紀錄
  • 排序 pair
• 預設沒有任何幹道被覆蓋到，預設為 0
• 用 for 找到一個加油站區段的左邊界 < 0
  • 因為我們不確定，現在這個加油站是不是最好的選擇，因此我們先準備一個暫存變數 temp
  • temp = 右邊界
  • 接續 for 循環，如果有一個加油站區段也符合左邊界 < 0，就檢查 temp 是否大於此加油站區段右邊界。
  • 如果有大於，那就讓 temp 改變成此加油站右邊界。
  • 找到一個必要的加油站。
• 讓 temp 變成加油站覆蓋幹道的左邊界，並且不斷執行 for 循環。(注意: 這裡的 for 與上一點 for 相同，且 i 是接續上一個點)

參考連結

Uva12321 -Gas Stations by txya900619

心得

其實這題沒有很難，就是他有一些小步驟要處理。
但是我沒有過這個灣，不太會反向思考嗎QQQQ 好難過，被電了一手，嗚嗚。

下次要學會反向思考，不要你不做的意思其實是要你做！　但我的腦袋總是編譯不成功這個意思嘛QQ

謝謝力瑋的 code 拉。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 100020
using namespace std;
int G, L, x, r;
vector<pair<int,int> > gas;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL

    while(cin >> L >> G, L > 0 && G > 0){
        gas.clear();
        for(int i = 0; i < G; i++){ //輸入加油站區段位置
            cin >> x >> r;
            gas.push_back({x-r, x+r});
        }
        sort(gas.begin(), gas.end()); //排序

        //coverage 當前覆蓋位置
        //temp_coverage 為分析中的 temp 含意
        //eliminated 可以消除的加油站
        int coverage = 0, temp_coverage = 0, eliminated = G, i = 0;
        while(L > coverage){ //如果當前覆蓋位置還沒有把幹道每個點都覆蓋
            temp_coverage = coverage; //先將 temp 設定為當前覆蓋位置的右邊界

            //for exit condition: 加油站的右邊界必須小於等於當前覆蓋區端
            for(; i < G && gas[i].first <= coverage; i++){ 
                //有辦法比 temp 還長，那就讓 temp 延長到 gas[i].second
                if(gas[i].second > temp_coverage) temp_coverage = gas[i].second;
            }
            if(coverage == temp_coverage) break; //如果沒變，表示無法繼續延長區段就跳出
            coverage = temp_coverage; // 延伸當前區段到 temp_coverage
            eliminated--; //必要的加油站多一個 = 能消除的加油站 -1
        }

        if(coverage < L) cout << "-1\n"; //如果沒辦法完整覆蓋幹道輸出 -1
        else cout << eliminated << "\n"; //輸出答案

    }

    return 0;
}