【題解】ZeroJudge b966: 第 3 題 線段覆蓋長度

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=b966
【解題想法】排序 【筆記】【筆記
【Tag】排序、貪心、掃描線

  • {a, b}:每個線段的「起點」座標 a 和「終點」座標 b。
  • 排序:a 由小到大排序,a 相同的話,b 由大到小排序。
  • 變數 s:目前線段的「起點」座標。
  • 變數 e:目前線段的「終點」座標。

【做法-1】掃描線的概念

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second

bool cmp(pii a, pii b) {
    if (a.first == b.first) {
        return a.second > b.second;
    } else {
        return a.first < b.first;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N, a, b;
    while (cin >> N) {
        vector<pii> v;
        for (int i=0; i<N; i++) {
            cin >> a >> b;
            v.push_back({a, b});
        }
        sort(v.begin(), v.end(), cmp);

        int s=0, e=0, ans=0;
        for (int i=0; i<v.size(); i++) {
            if (v[i].F >= e) {
                ans += (e-s);
                s = v[i].F;
                e = v[i].S;
            } else if (v[i].S > e) {
                e = v[i].S;
            }
        }
        ans += (e-s);
        cout << ans << endl;
    }
    return 0;
}

【做法-2】換個角度思考

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int N, L, R;
    cin >> N;
    vector<pair<int,int>> v;
    for (int i = 0; i < N; i++) {
        cin >> L >> R;
        //把線段的開始端點和結束端點視為獨立的evnet
        //在線段的開始端點L處,event +1
        v.push_back({L, 1});
        //在線段的結束端點R處,event -1
        v.push_back({R, -1});
    }
    sort(v.begin(), v.end());
    //now指向目前檢視的event
    //event為該座標點i, 對應一個左閉由開區間[i, i+1), 共被幾段線段覆蓋
    int now = 0, event = 0, ans = 0;
    for (int i = 0; i <= 1e7; i++) {
        while (now < (int)v.size() && v[now].first == i) {
            event += v[now].second;
            now++;
        }
        if (event > 0) {
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}

while True:
    try:
        n = int(input())
        lst = []
        for i in range(n):
            l, r = map(int, input().split())
            lst.append([l, r])
        lst.sort(key = lambda x:(x[0], x[1]))
        for i in range(1, len(lst)):
            if lst[i][1] < lst[i-1][1]:
                lst[i] = lst[i-1]
                lst[i-1] = []
            elif lst[i-1][1] < lst[i][0]:
                continue
            else:
                lst[i][0] = lst[i-1][0]
                lst[i-1] = []
        count = 0
        for part in lst:
            if part != []:
                count += (part[1]-part[0])
                
        print(count)
    except:
        break
分享本文 Share with friends