# 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++`
Sign in with Wallet
Connect another wallet