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