APCS 線段覆蓋長度 (zerojudge b966/f855)

發表於 更新於 分類於 ， 閱讀次數： 文章字數： 452 所需閱讀時間 ≈ 2 分鐘

題目網址 (測資加強版)

給定一維座標上一些線段，求這些線段所覆蓋的長度，注意，重疊的部分只能算一次。 例如給定 4 個線段 (5, 6)、(1, 2)、(4, 8)、(7, 9)，如下圖，線段覆蓋長度為 6 (包含 1～2、4～9)。 覆蓋了12、49共6個格子

解題思路： 如果直接開個陣列記錄每格格子走過了沒，最後再去檢查，但時間複雜度會是 \(O(NL)\) 會到 10^11 次方 (L 代表座標範圍)，肯定會 TLE，改成用 priority queue（Heap）去存輸入，讓左界是由小到大排列（或者一開始用陣列儲存之後再 sort，時間複雜度一樣不變是 \(O(N log N)\) ），並紀錄目前右界最大值，就可以確定後續資料的左界不會比前面的小，並用 result 紀錄目前覆蓋的格子數，這樣只要判斷以下兩種狀況

  1. 輸入的左界目前右界最大值還大：將 result 加上整段區間長度，並更新右界最大值為輸入的右界
  2. 輸入的左界目前右界最大值小且輸入的右界也比前右界最大值大：將 result 加上輸入右界到目前最大值的範圍，並更新右界最大值為輸入的右界 （若輸入的左界目前右界最大值小且輸入的右界也比前右界最大值小，則目前這個區間都在目前已涵蓋的格子內）

而如此一來就可以讓時間複雜度小至 \(O(N log N)\)，能夠在題目給定時間內完成

🌟 可以搭配 pair 使用會比較方便

APCS 線段覆蓋長度 
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
#include <bits/stdc++.h>
#define pii pair<int, int>
#define l first
#define r second
using namespace std;

priority_queue<pii, vector<pii>, greater<pii> > pq;
int n;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>> n;
    for(int i = 0, tmp1, tmp2; i<n; i++)
        cin >> tmp1 >> tmp2, pq.push(make_pair(tmp1, tmp2));
    int max=pq.top().l, result=0;
    while(!pq.empty()) {
        pii cur = pq.top();
        pq.pop();
        if(cur.r<=max) continue;
        else if(cur.first<=max) result+=cur.r-max, max=cur.r;
        else result+=(cur.r-cur.l), max=cur.r;
    }

    cout << result << '\n';
    
    return 0;
}

AC的Submission～ zerojudge f855 測資加強版