---
# System prepended metadata

title: 0-14 常用工具/函式
tags: [演算法, C++, APCS, Python]

---

# 0-14 常用工具/函式

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

## [TOJ: 55 / Number](https://toj.tfcis.org/oj/pro/55/)

### Python 程式碼

用 collections 函式庫的 Counter 計數，但是第3筆測資記憶體爆掉。
```python=
from collections import Counter

n = int(input())
songs = list(map(int, input().split()))
cnt = Counter(songs)  # 計數器，計算各個編號歌曲的數量
m = int(input())
for _ in range(m):
    print(cnt[int(input())])
```

改用 bisect 函式庫 bisect_right 及 bisect_left，數量即為兩者回傳值的差，但是第3筆測資記憶體爆掉。
```python=
from bisect import bisect_left, bisect_right

n = int(input())
songs = sorted(list(map(int, input().split())))
m = int(input())
for _ in range(m):
    i = int(input())
    print(bisect_right(songs, i) - bisect_left(songs, i))
```


### C++ 程式碼

用 map 字典計數，執行時間最久約為 1697 ms，使用記憶體最多約為 48944 kB，通過測試。
```cpp=
#include <iostream>
#include <map>
using namespace std;

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int N, M, song; cin >> N;
    map<int, int> songs;
    for(int i=0; i<N; i++) {
        cin >> song;
        songs[song]++;
    }
    cin >> M;
    for(int i=0; i<M; i++) {
        cin >> song;
        cout << songs[song] << "\n";
    }
    return 0;
}
```

用 unordered_map 字典計數會更快，執行時間最久約為 784 ms，使用記憶體最多約為 40604 kB，通過測試。
```cpp=
#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int N, M, song; cin >> N;
    unordered_map<int, int> songs;
    for(int i=0; i<N; i++) {
        cin >> song;
        songs[song]++;
    }
    cin >> M;
    for(int i=0; i<M; i++) {
        cin >> song;
        cout << songs[song] << "\n";
    }
    return 0;
}
```

改用 algorithm 函式庫 upper_bound 及 lower_bound，數量即為兩者回傳值的差，執行時間最久約為 898 ms，使用記憶體最多約為 6164 kB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int N; cin >> N;
    int songs[N];
    for(int i=0; i<N; i++) cin >> songs[i];
    sort(songs, songs+N);
    int M; cin >> M;
    for(int i=0, x; i<M; i++) {
        cin >> x;
        cout << upper_bound(songs, songs+N, x) - lower_bound(songs, songs+N, x) << "\n";
    }
    return 0;
}
```

## [TOJ: 47 / PB magic spell](https://toj.tfcis.org/oj/pro/47/)

### Python 程式碼

使用二分搜尋法，會遇到 RuntimeError。
```python=
from bisect import bisect_left

n = int(input())
xs = sorted(list(map(int, input().split())))
t = int(input())
for _ in range(t):
    k = int(input())
    idx = bisect_left(xs, k)
    if idx == n:  # k 大於 xs 中的最大值
        print(f"{xs[-1]:d} no")  # 只有小於 k 的值，其中的最大值是最後一項
    elif xs[idx] == k:  # 如果 xs[idx] 等於 k
        print(k)  # 印出 k
    elif idx == 0:  # k 小於 xs 中的最小值
        print(f"no {xs[0]:d}")  # 只有大於 k 的值，其中的最小值是第0項
    else:  # k 介於 xs 的數值之間
        print(f"{xs[idx-1]:d} {xs[idx]:d}")
```

先判斷 k 是否小於最小值或大於最大值，如果不是再用二分搜尋法，但還是會遇到 RuntimeError。
```python=
from bisect import bisect_left

n = int(input())
xs = sorted(list(map(int, input().split())))
t = int(input())
imin, imax = xs[0], xs[-1]
for _ in range(t):
    k = int(input())
    if k < imin:  # k 小於 xs 中的最小值
        print(f"no {imin:d}")  # 只有大於 k 的值，其中的最小值是 imin
    elif k > imax:  # k 大於 xs 中的最大值
        print(f"{imax:d} no")  # 只有小於 k 的值，其中的最大值是 imax
    else:  # k 介於 xs 的數值之間
        idx = bisect_left(xs, k)  # 二分搜尋法，找出於 xs 插入 k 的索引值
        if xs[idx] == k:  # 如果 xs[idx] 等於 k
            print(k)  # 印出 k
        else:   # 印出小於 k 的最大值、大於 k 的最小值
            print(f"{xs[idx-1]:d} {xs[idx]:d}")
```

### C++ 程式碼

使用二分搜尋法，超時。
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    int xs[n];
    for(int i=0; i<n; i++) cin >> xs[i];
    sort(xs, xs+n);
    int t; cin >> t;
    for(int i=0; i<t; i++) {
        int k; cin >> k;
        int idx = lower_bound(xs, xs+n, k) - xs;
        if (idx == n) {  // k 大於 xs 中的最大值
            cout << xs[n-1] << " no\n";  // 只有小於 k 的值，其中的最大值是最後一項
        } else if (xs[idx] == k) {  // 如果 xs[idx] 等於 k
            cout << k << "\n";  // 印出 k
        } else if (idx == 0) {  // k 小於 xs 中的最小值
            cout << "no " << xs[0] << "\n";  // 只有大於 k 的值，其中的最小值是第0項
        } else {  // k 介於 xs 的數值之間
            cout << xs[idx-1] << " " << xs[idx] << "\n";
        }
    }
    return 0;
}
```

先判斷 k 是否小於最小值或大於最大值，如果不是再用二分搜尋法，執行時間最久約為 158 ms，使用記憶體最多約為 4372 kB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    int xs[n];
    for(int i=0; i<n; i++) cin >> xs[i];
    sort(xs, xs+n);
    int imin = xs[0], imax = xs[n-1];
    int t; cin >> t;
    for(int i=0; i<t; i++) {
        int k; cin >> k;
        if (k < imin) {  // k 小於 xs 中的最小值
            cout << "no " << imin << "\n";  // 只有大於 k 的值，其中的最小值是 imin
        } else if (k > imax) {  // k 大於 xs 中的最大值
            cout << imax << " no\n";  // 只有小於 k 的值，其中的最大值是 imax
        } else {
            int idx = lower_bound(xs, xs+n, k) - xs;
            if (xs[idx] == k) {  // 如果 xs[idx] 等於 k
                cout << k << "\n";  // 印出 k
            } else {  // k 介於 xs 的數值之間
                cout << xs[idx-1] << " " << xs[idx] << "\n";
            }
        }
    }
    return 0;
}
```

------

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