---
# System prepended metadata

title: 0-20 set
tags: [演算法, C++, APCS, Python]

---

# 0-20 set

講義不是我寫的，網址在此 https://emanlaicepsa.github.io/2020/10/21/0-index/
我只是將自己寫的練習題程式碼記錄下來。
最後更新日期：2024年10月10日

## [TIOJ: 1911. 雲端列印](https://tioj.ck.tp.edu.tw/problems/1911)

### Python 程式碼

這個題目輸入的工作優先權有重複的數字，如果用解題 Python 不能使用 set，但如果用 list 需要在每次加入資料時再 sort 一次，會拖慢執行的時間，在第24、25、26、27、29筆測資會超時。
```python=
data = list(map(int, input().split()))
task = []
ans = []
for d in data:
    if d == 0: break
    if d > 0:
        task.append(d)
        task.sort()
    else:
        if not task: continue
        if d == -1: ans.append(task.pop(0))
        elif d == -2: ans.append(task.pop())
print(*ans)
```

比較好的作法應該是用 [bisect](https://docs.python.org/3/library/bisect.html) 函式庫中的 insort_left，將新的資料 d 插入串列 task 並保持資料由小到大排序，這樣的寫法效率較好，只剩下第25、29筆測資會超時。
```python=
from bisect import insort_left

data = list(map(int, input().split()))
task = []
ans = []
for d in data[:-1]:
    if d == 0: break
    if d > 0:
        insort_left(task, d)
    else:
        if not task: continue
        if d == -1: ans.append(task.pop(0))
        elif d == -2: ans.append(task.pop())
print(*ans)
```


如果想要在 Python 使用附帶排序功能的容器，需要另外安裝 [sortedcontainers](https://grantjenks.com/docs/sortedcontainers/) 函式庫，安裝指令為
```shell
pip3 install sortedcontainers
```
但是通常 on-line judge 的機器不支援這個函式庫。
```python=
data = list(map(int, line.split()))
task = SortedList()
ans = []
for d in data:
    if d == 0: break
    if d > 0: task.add(d)
    else:
        if not task: continue
        if d == -1: ans.append(task.pop(0))
        elif d == -2: ans.append(task.pop())
print(*ans)
```

### C++ 程式碼

執行時間共 636 ms，使用記憶體最多約為 18196 kB，通過測試。
```cpp=
#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int d;  // 暫存資料用的變數 d
    multiset<int> task;  // 儲存列印工作的 nultiset，資料由大到小排序
    while(cin >> d) {
        if (d == 0) break;
        if (d > 0) {
            task.insert(d);
        } else {
            if (task.empty()) continue;
            if (d == -1) {
                cout << *task.begin() << " ";
                task.erase(task.begin());
            } else if (d == -2) {
                auto it = task.end();
                it--;
                cout << *it << " ";
                task.erase(it);
            }
        }
    }
    cout << "\n";
    return 0;
}
```
## [ZeroJudge: b938. kevin 愛殺殺](https://zerojudge.tw/ShowProblem?problemid=b938)

這題用 set 會太慢。

### Python 程式碼

第10筆測資開始遇到 MemoryError。
```python=
n, m = map(int, input().split())  # 讀取人數 n，要淘汰的人數 m
kill = list(map(int, input().split()))  # 要淘汰指定編號的下一個人
p = [-1] + [i+1 for i in range(1, n)] + [-1]  # 每個人對應的淘汰目標編號，最前面及第n個人的目標為 -1

for k in kill:  # 依序讀取名單
    if p[k] != -1:  # 如果編號 k 的人還沒有被淘汰且後方有人
        t = p[k]  # 要淘汰的目標編號 t
        print(t)  # 印出 t
        p[k] = p[t]  # 將編號 k 的目標改為編號 t 的目標
        p[t] = -1  # 編號 t 被淘汰，目標改為 -1
    else:  # 否則印出 0u0 ...... ?
        print("0u0 ...... ?")
```

### C++ 程式碼

執行時間最久約為 0.3 s，使用記憶體最多約為 8 MB，通過測試。
```cpp=
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;  // 讀取人數 n，要淘汰的人數 m
    int kill[m];  // 要淘汰指定編號的下一個人
    for(int i=0; i<m; i++) cin >> kill[i];  // 讀取 m 筆資料
    int p[n+1];  // 每個人對應的淘汰目標編號，長度開 n+1，索引值對應到人的編號，自己已經被淘汰或後方沒人則目標為 -1
    for(int i=1; i<=n; i++) p[i] = i+1;  // 每個人目標預設為下一個
    p[0] = -1;  // 先設定編號 0 的人目標為 -1
    p[n] = -1;  // 先設定編號 n 的人目標為 -1
    for(int i=0; i<m; i++) {  // 依序讀取名單
        int k = kill[i];  // 編號 k
        if (p[k] != -1) {  // 如果編號 k 的人還沒有被淘汰且後方有人
            int t = p[k];  // 要淘汰的目標編號 t
            cout << t << "\n";  // 印出 t
            p[k] = p[t];  // 將編號 k 的目標改為編號 t 的目標
            p[t] = -1;  // 編號 t 被淘汰，目標改為 -1
        } else {  // 否則印出 0u0 ...... ?
            cout << "0u0 ...... ?\n";
        }
    }
    return 0;
}
```

改用 cstdio 函式庫的 scanf 及 printf，執行時間最久約為 0.3 s，使用記憶體最多約為 7.7 MB，通過測試。
```cpp=
#include <cstdio>
using namespace std;

int main() {
    int n, m; scanf("%d %d", &n, &m);  // 讀取人數 n，要淘汰的人數 m
    int kill[m];  // 要淘汰指定編號的下一個人
    for(int i=0; i<m; i++) {
        int k; scanf("%d", &k); kill[i] = k;  // 讀取 m 筆資料
    }
    int p[n+1];  // 每個人對應的淘汰目標編號，長度開 n+1，索引值對應到人的編號，自己已經被淘汰或後方沒人則目標為 -1
    for(int i=1; i<=n; i++) p[i] = i+1;  // 每個人目標預設為下一個
    p[0] = -1;  // 先設定編號 0 的人目標為 -1
    p[n] = -1;  // 先設定編號 n 的人目標為 -1
    for(int i=0; i<m; i++) {  // 依序讀取名單
        int k = kill[i];  // 編號 k
        if (p[k] != -1) {  // 如果編號 k 的人還沒有被淘汰且後方有人
            int t = p[k];  // 要淘汰的目標編號 t
            printf("%d\n", t);  // 印出 t
            p[k] = p[t];  // 將編號 k 的目標改為編號 t 的目標
            p[t] = -1;  // 編號 t 被淘汰，目標改為 -1
        } else {  // 否則印出 0u0 ...... ?
            printf("0u0 ...... ?\n");
        }
    }
    return 0;
}
```

## [TOJ: 275 / 2015南市賽校內模擬賽 - Problem 3](https://toj.tfcis.org/oj/pro/275/)

### Python 程式碼

執行時間最久約為 1925 ms，使用記憶體最多約為 9748 kB，通過測試。
```python=
from bisect import insort_left

big, small = [], []   # 分成大、小兩堆數字
n = int(input())      # 輸入資料行數
for i in range(1, n+1):   # 讀取 n 行資料
    x = int(input())      # 讀取資料存入 x
    if i == 1 or x < small[-1]:   # 如果是第1筆資料或是小於 small 之中的最大值（最後一筆）
        insort_left(small, x)   # 將 x 加入 small 並由小到大排序
    else:   # 反之將 x 加入 big 並由小到大排序
        insort_left(big, x)

    while len(big) > i//2: small.append(big.pop(0))
    while len(big) < i//2: big.insert(0, small.pop())

    if i&1: ans = float(small[-1])
    else: ans = (small[-1] + big[0]) / 2.0
    print("{:.6f}".format(ans))
```

### C++ 程式碼

執行時間最久約為 124 ms，使用記憶體最多約為 6776 kB，通過測試。
```cpp=
#include <iostream>
#include <set>
#include <iomanip>
using namespace std;

multiset<unsigned int> big, small;  // 輸入資料可能會重複，要用 multiset
void pop_small();
void pop_big();

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    unsigned int n; cin >> n;
    for(size_t i=1, x; i<=n; i++) {
        cin >> x;
        if (i == 1 || x < *small.rbegin()) small.insert(x); 
        else big.insert(x);
        while(big.size() > i/2) pop_big();
        while(big.size() < i/2) pop_small();
        double ans;
        cout << fixed << setprecision(6);
        if (i&1) ans = *small.rbegin() * 1.0;
        else ans = (*small.rbegin() + *big.begin())*1.0/2.0;
        cout << ans << "\n";
    }
    return 0;
}

void pop_small() {
    big.insert(*small.rbegin());
    small.erase(*small.rbegin());
}

void pop_big() {
    small.insert(*big.begin());
    big.erase(*big.begin());
}
```

## [TIOJ: 1161. 4.虛擬番茄online](https://tioj.ck.tp.edu.tw/problems/1161)

### Python 程式碼

程式碼運作邏輯與底下的 C++ 版本相同，但是無法通過測試，第4筆測資超過記憶體上限。
```python=
from bisect import insort_left

T = int(input())  # 測試資料組數
for _ in range(T):
    s = []  # 儲存目前需要的能力值，由小到大排序
    n, k = map(int, input().split())  # 可以學的技能總數 n，要學的技能總數 k
    sa = []  # 學習各技能需要的能力值 s、a
    for _ in range(n): sa.append(list(map(int, input().split())))  # 讀取資料給 sa
    sa.sort()  # 由小到大排序
    ans = 1000000001  # 答案先預設為很大的值
    for i in range(n):  # 依序讀取 sa 的資料
        insort_left(s, sa[i][1])  # 於 s 插入 sa[i][1] 並保持順序
        if len(s) > k: s.pop()  # 如果 s 的數量大於 k，移除最後一項
        if len(s) == k:  # 如果 s 的數量等於 k，更新 ans 為 ans 及 sa[i][0] + s[-1] 較小值
             ans = min(ans, sa[i][0] + s[-1])
    print(ans)
```

### C++ 程式碼

執行時間共約為 920 ms，使用記憶體最多約為 34780 kB，通過測試。
```cpp=
#include <iostream>
#include <set>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;  // 測試資料組數
    for(int i=0; i<T; i++) {
        multiset<int, greater<int>> s;  // 儲存目前需要的能力值，由大到小排序
        int n, k; cin >> n >> k;  // 可以學的技能總數 n，要學的技能總數 k
        pair<int, int> sa[n];  // 學習各技能需要的能力值 s、a
        for(int i=0; i<n; i++) cin >> sa[i].first >> sa[i].second;  // 讀取資料給 sa
        sort(sa, sa+n);  // 由小到大排序
        int ans = 1000000001;  // 答案先預設為很大的值
        for(int i=0; i<n; i++) {  // 依序讀取 sa 的資料
            s.insert(sa[i].second);  // 於 s 插入 sa[i].second 並保持順序
            if (s.size() > (size_t)k) s.erase(s.begin());  // 如果 s 的數量大於 k，移除第一項
            if (s.size() == (size_t)k)  // 如果 s 的數量等於 k，更新 ans 為 ans 及 sa[i].first + *s.begin() 較小值
                 ans = min(ans, sa[i].first + *s.begin());
        }
        cout << ans << "\n";
    }
    return 0;
}
```
## [TOJ: 512 / F. 樓層交換](https://toj.tfcis.org/oj/pro/512/)

### Python 程式碼

第4筆測資超時。
```python=
n, q = map(int, input().split())  # 樓層數 n，事件數 q
floor = [i for i in range(n+1)]  # 各高度的樓層編號，前方加入一個用不到的 0
correct = floor.copy()  # 編號i樓層目前所在的高度
for _ in range(q):  # 執行 q 次
    t, a, b = map(int, input().split())  # 事件種類 t，目標高度a、b
    if t == 1:  # 第1種事件，高度a、b樓層互換
        correct[floor[a]] = b  # 原來於高度a的樓層編號移到高度b
        correct[floor[b]] = a  # 原來於高度b的樓層編號移到高度a
        floor[a], floor[b] = floor[b], floor[a]  # 交換編號
    elif t == 2:  # 第2種事件，復原高度a到b的樓層
        ans = 0  # 答案
        for i in range(a, b+1):
            if floor[i] != i:  # 有效交換，高度 i 的樓層編號不等於 i
                ans += 1  # 答案加 1
                j = correct[i]  # 編號 i 目前位於高度 j
                correct[i] = i  # 編號 i 回到高度 i
                correct[floor[i]] = j  # 目前高度 i 的樓層編號移到 j
                floor[i], floor[j] = i, floor[i]  # 高度 i 的樓層編號為 i，高度 j 的樓層編號為原來高度 i 的樓層編號
        print(ans)  # 印出答案
```

改用 set，第4筆測資超時。
```python=
wrong = set()  # 高度錯誤的樓層
n, q = map(int, input().split())  # 樓層數 n，操作次數 q
arr = [i for i in range(n+1)]  # 各高度的樓層編號 arr
correct = arr.copy()  # 各編號的樓層現在的高度 correct

def change(x, y):  # 自訂函式，交換高度 x、y 的樓層
    wrong.discard(x)  # 從 wrong 移除 x，要用 discard 才不會在 x 不存在時回傳錯誤訊息
    wrong.discard(y)  # 從 wrong 移除 y
    arr[x], arr[y] = arr[y], arr[x]  # 交換高度 x、y 對應的樓層編號
    correct[arr[x]] = x  # 編號 arr[x] 的樓層目前位於高度 x
    correct[arr[y]] = y  # 編號 arr[y] 的樓層目前位於高度 y
    if arr[x] != x: wrong.add(x)  # 如果 arr[x] 編號不等於 x，編號 x 放錯高度，加入 wrong
    if arr[y] != y: wrong.add(y)  # 如果 arr[y] 編號不等於 y，編號 y 放錯高度，加入 wrong

def recover(x, y):  # 自訂函式，回復高度 x、y 的樓層，印出有效操作次數
    ans = 0  # 有效操作次數
    for i in range(x, y+1):  # 依序處理高度 x 到 y 的樓層
        if not wrong or i > max(wrong): break  # 如果 wrong 是空的或 i 大於 wrong 的最大值，不會再有有效操作，中止迴圈
        elif i in wrong:  # 如果高度 i 在 wrong 之中
            ans += 1  # 答案加 1
            change(correct[i], i)  # 呼叫 change，交換兩者
    return ans  # 回傳答案

for _ in range(q):  # 執行 q 次
    op, a, b = map(int, input().split())  # 讀取操作種類 op，高度 a、b
    if op == 1: change(a, b)
    else: print(recover(a, b))
```

如果要維持資料由小到大或由大到小排序，在 C++ 可以用 set，在 Python 要用 list 及 bisect.insort_left。第4筆測資超時。
```python=
from bisect import bisect_left, insort_left

wrong = []  # 高度錯誤的樓層
n, q = map(int, input().split())  # 樓層數 n，操作次數 q
arr = [i for i in range(n+1)]  # 各高度的樓層編號 arr
correct = arr.copy()  # 各編號的樓層現在的高度 correct

def change(x, y):  # 自訂函式，交換高度 x、y 的樓層
    if x in wrong: wrong.remove(x)  # 從 wrong 移除 x
    if y in wrong: wrong.remove(y)  # 從 wrong 移除 y
    arr[x], arr[y] = arr[y], arr[x]  # 交換高度 x、y 對應的樓層編號
    correct[arr[x]] = x  # 編號 arr[x] 的樓層目前位於高度 x
    correct[arr[y]] = y  # 編號 arr[y] 的樓層目前位於高度 y
    if arr[x] != x: insort_left(wrong, x)  # 如果 arr[x] 編號不等於 x，編號 x 放錯高度，加入 wrong
    if arr[y] != y: insort_left(wrong, y)  # 如果 arr[y] 編號不等於 y，編號 y 放錯高度，加入 wrong

def recover(x, y):  # 自訂函式，回復高度 x、y 的樓層，印出有效操作次數
    ans = 0  # 有效操作次數
    for i in range(x, y+1):  # 依序處理高度 x 到 y 的樓層
        idx = bisect_left(wrong, i)  # 於 wrong 搜尋 i
        if idx == len(wrong): break  # 如果 i 大於 wrong 的最大值，不會再有有效操作，中止迴圈
        elif wrong[idx] == i:
            ans += 1  # 答案加 1
            change(correct[i], i)  # 呼叫 change，交換兩者
    return ans  # 回傳答案

for _ in range(q):  # 執行 q 次
    op, a, b = map(int, input().split())  # 讀取操作種類 op，高度 a、b
    if op == 1: change(a, b)
    else: print(recover(a, b))
```

### C++ 程式碼


第4筆測資超時。
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;  // 樓層數 n，事件數 q
    int floor[n+1], correct[n+1];  // 樓層編號，前方加入一個用不到的 0；第i樓層目前所在的高度
    for(int i=1; i<=n; i++) floor[i] = correct[i] = i;
    for(int k=0; k<q; k++) {  // 執行 q 次
        int t, a, b; cin >> t >> a >> b;  // 事件種類 t，目標高度a、b
        if (t == 1) {  // 第1種事件，高度a、b樓層互換
            correct[floor[a]] = b;  // 原來於高度a的樓層編號移到高度b
            correct[floor[b]] = a;  // 原來於高度b的樓層編號移到高度a
            swap(floor[a], floor[b]);  // 交換編號
        } else {  // 第2種事件，復原高度a到b的樓層
            int ans = 0;  // 答案
            for(int i=a; i<=b; i++) {
                if (floor[i] != i) {  // 有效交換，高度 i 的樓層編號不等於 i
                    ans++;  // 答案加 1
                    int j = correct[i];  // 編號 i 目前位於高度 j
                    correct[i] = i;  // 編號 i 回到高度 i
                    correct[floor[i]] = j;  // 目前高度 i 的樓層編號移到 j
                    floor[j] = floor[i];  // 高度 j 的樓層編號為原來高度 i 的樓層編號
                    floor[i]  = i;  // 高度 i 的樓層編號為 i
                }
            }
            cout << ans << "\n";  // 印出答案
        }
    }
    return 0;
}
```

因為 C++ 的 set erase 回傳值是移除的資料數量，如果要移除的資料不在 set 之中會回傳 0，不會有錯誤訊息。如果用講義上的程式碼寫法比較好，執行時間最久約為 587 ms，使用記憶體最多約為 25720 kB，通過測試。
```cpp=
#include <iostream>
#include <set>
#include <algorithm>  // for swap
using namespace std;

set<int> wrong;  // 高度錯誤的樓層
int n, q;  // 樓層數 n，操作次數 q
int arr[1000005], correct[1000005];  // 各高度的樓層編號 arr，各編號的樓層現在的高度 correct

void change(int x, int y) {  // 自訂函式，交換高度 x、y 的樓層
    wrong.erase(x);  // 從 wrong 移除 x
    wrong.erase(y);  // 從 wrong 移除 y
    swap(arr[x], arr[y]);  // 交換高度 x、y 對應的樓層編號
    correct[arr[x]] = x;  // 編號 arr[x] 的樓層目前位於高度 x
    correct[arr[y]] = y;  // 編號 arr[y] 的樓層目前位於高度 y
    if(arr[x] != x) wrong.insert(x);  // 如果 arr[x] 編號不等於 x，編號 x 放錯高度，加入 wrong
    if(arr[y] != y) wrong.insert(y);  // 如果 arr[y] 編號不等於 y，編號 y 放錯高度，加入 wrong
}

int recover(int x, int y) {  // 自訂函式，回復高度 x、y 的樓層，印出有效操作次數
    int ans = 0;  // 有效操作次數
    while(true) {  // 無窮迴圈
        auto it = wrong.lower_bound(x);  // 於 wrong 搜尋 x，要用 set 的 lower_bound
        if(it == wrong.end() || *it > y) break;  // 如果沒有找到 x 或是 *it 大於 y，不會再有有效操作，中止迴圈
        ans++;  // 答案加 1
        change(correct[*it], *it);  // 呼叫 change，交換兩者
    }
    return ans;  // 印出答案
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for(int i=1; i<=n; i++) arr[i] = correct[i] = i;
    for(int i=1, op, a, b; i<=q; i++){
        cin >> op >> a >> b;
        if(op == 1) change(a, b);
        else cout << recover(a, b) << "\n";
    }
    return 0;
}
```


## [TOIJ: 1941. 直升機抓寶 (Helicopter)](https://tioj.ck.tp.edu.tw/problems/1941)

### Python 程式碼

從第24筆測資開始超時。
```python=
from bisect import bisect_right, insort_left

s = []  # 目前能捕捉的寶可夢重疊區域
n = int(input())  # 地圖範圍為 (1, 1) ~ (n, n)，共有 n 隻寶可夢
for _ in range(n):  # 檢測 n 次
    le, ri = map(int, input().split())  # 可以捕捉第 i 隻寶可夢的範圍
    insort_left(s, le)  # 將 le 插入 s 並保持順序
    idx = bisect_right(s, ri)  # 找出於 s 插入 ri 的索引值，若有同樣的資料加在最右側 
    if idx != len(s): s.pop(idx)  # 如果 idx 沒有出界，移除 s[idx]
print(len(s))
```

### C++ 程式碼

**注意事項：要用 set 內部的 upper_bound**，不能使用 algorithm 的 upper_bound。總執行時間約為 11711 ms，使用記憶體最多約為 17212 kB，通過測試。
```cpp=
#include <iostream>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    multiset<int> s;  // 目前能捕捉的寶可夢重疊區域
    int n; cin >> n;  // 地圖範圍為 (1, 1) ~ (n, n)，共有 n 隻寶可夢
    for(int i=0, le, ri; i<n; i++) {  // 檢測 n 次
        cin >> le >> ri;  // 可以捕捉第 i 隻寶可夢的範圍
        s.insert(le);  // 將 le 插入 s 並保持順序
        auto it = s.upper_bound(ri);  // 找出於 s 插入 ri 的索引值，若有同樣的資料加在最右側 
        if (it != s.end()) s.erase(it);  // 如果 it 沒有出界，移除 it
    }
    cout << s.size() << "\n";
    return 0;
}
```

------

###### tags:`演算法`、`APCS`、`Python`、`C++`