# 排序與搜尋 ## 3/1 社課 --- ## 排序 ---- 簡單來講 就是某些題目需要讓序列按照某種順序排列 就需要排序 ---- **std::sort !!** ~~他太好用了所以我們就只講他吧~~ ---- ``#include <algorithm>`` 如何 sort 一個序列 ```cpp= sort(begin_iter, end_iter, comp_func); ``` `begin_iter` 和 `end_iter` 就是儲存資料的位址 如果用靜態陣列，第 $i$ 個就是 `arr+i` 如果用 vector 那就是 `v.begin()+i` 左閉右開區間 ---- ### compare_function 排序的方法 不輸入的話就是預設排序（由小到大排序） 否則這裡需要輸入一個比較函式 ---- ### 比較函式的輸入方法 ```cpp= bool cmp(data_type a, data_type b){ // ... } ``` - 回傳值是布林值 - `data_type` 是你要排序的資料型態 - 要回傳的就是 **a 是否要排在 b 前面** - 不能發生 `cmp(a, b)=cmp(b, a)=true` 的情況 ---- 排序成遞減序列 ```cpp= bool cmp(int a, int b){ return a>b; // 不能有等號 } ``` ---- 複雜度 $O(n\log{n})$ ---- [TOI 2023 pA. 房屋推薦 (house)](https://zerojudge.tw/ShowProblem?problemid=k184)  ---- 用剛剛的 sort 怎麼排？ ---- 直接照他想要的順序排！ ```cpp= struct house{ int id, r; long long x, y; long long mnd=9e18; } arr[100005]; bool cmp(house a, house b){ if(a.mnd!=b.mnd) return a.mnd<b.mnd; if(a.r!=b.r) return a.r<b.r; return a.id<b.id; } ``` 對每個捷運站找最小距離平方 然後就可以排序，複雜度 $O(nm+n\log{n})$ 很緊，要加 IO 優化才會過 --- ## 搜尋 --- ## 暴搜（枚舉） ---- 在某些範圍很小的題目 可以枚舉每一種情況 ---- ### [ABC 335 B - Tetrahedral Number](https://atcoder.jp/contests/abc335/tasks/abc335_b) 找出所有非負整數 $(x,y,z)$ 滿足 $x+y+z\le N$ 按字典序輸出 $0\le N\le 21$ ---- 看到 $N$ 很小 就知道可以枚舉 ---- 因為要照字典序排 所以就按 $x,y,z$ 的順序枚舉 ```cpp= #include<bits/stdc++.h> #define fastio ios::sync_with_stdio(0); cin.tie(0); using namespace std; int n; int main(){ fastio cin >> n; for(int i=0; i<=n; i++){ for(int j=0; i+j<=n; j++){ for(int k=0; i+j+k<=n; k++){ cout << i << ' ' << j << ' ' << k << '\n'; } } } } ``` ---- ### 怎麼找質因數 ---- 從 $1$ 找到 $N$ 看是不是整除？ $O(n)$ 太慢了 ---- 縮小範圍一下 一個數字 $N$ 不會有超過一個 $\ge\sqrt{N}$ 的質因數 所以我們只需要枚舉到 $\sqrt{N}$ 就好了！ ---- $O(\sqrt{N})$ ```cpp= #include<bits/stdc++.h> #define fastio ios::sync_with_stdio(0); cin.tie(0); using namespace std; int n; int main(){ fastio cin >> n; for(int i=2; i<=sqrt(n); i++){ int a=0; while(n%i==0){ // i 整除 n if(a==0) cout << i; n/=i; a++; } if(a>1) cout << "^" << a; // 指數大於 1 if(n==1) break; // 質因數分解完了 if(a!=0) cout << " * "; } if(n>1) cout << n << '\n'; // 大於 sqrt(n) 的質因數 } ``` --- ## 二分搜 ---- **猜數字遊戲** 在範圍 $[1,1000]$ 裡猜一個數字 $n$ 如果猜的數字 $x<n$ 會告訴你太小了 如果猜的數字 $x>n$ 會告訴你太大了 怎麼猜比較快？ ---- 如果現在猜了一個數字 $x<n$ 那就表示 $\le x$ 的數都是不可能的 所以猜的範圍就變小了 ---- 那就每次都猜範圍內的最中間！ 每次範圍都會少一半 複雜度 $O(\log{n})$！ （在計算機當中 $\log{}$ 常代表 $\log_2{}$） ---- ```cpp= int l=0, r=1000; while(r-l>1){ int mid=(l+r)/2; if(mid<n) l=mid; else r=mid; } ``` ---- 最後答案是什麼？ ---- $r$ 都是大於等於 $n$ 的 $l$ 都是小於 $n$ 的 也就是 $l$ 不可能等於 $n$ 最後答案就是 $r$ ---- **實作細節** 要注意 $l$ 和 $r$ 分別代表兩種狀態 像上面這個 $l$ 就是小於 $n$ 的 $r$ 就是大於等於 $n$ 的 所以 `mid=(r+l)/2` 如果 $mid$ 小於 $n$ 就要讓 $l=mid$，反之亦然 ---- 如果 $(l+r)/2$ 會溢位 可以用 $l+(r-l)/2$ 達到同樣的效果 ---- 抱著上面的想法 我們可以歸納出 把整段數字分成 **符合條件的** 和 **不符合的** 分別代表兩邊 然後再用二分搜縮小範圍 ---- ### [APCS 2017-0304-4基地台](https://zerojudge.tw/ShowProblem?problemid=c575) 要設置基地台 假設在點 $x$ 設置了一個基地台 範圍 $[x-\frac{D}{2}, x+\frac{D}{2}]$ 都會被覆蓋到 現在給定 $N$ 個點座標，最多能蓋 $K$ 個基地台 求 $D$ 最少要多少才能覆蓋到所有點 （基地座標可以是浮點數） ---- 既然他要求長度 那就對長度做二分搜！ ---- 每次看看某個長度 能不能把需要建造的基地台數壓到 $K$ 個以下 如果長度 $D$ 可以，那長度 $D+1$ 一定可以！ 所以問題就回到了 **可以/不可以** 兩種情況了 二分搜！ ---- 至於判斷可不可以 就從左掃到右 一旦有一個沒被前面放的那個掃到 就把這裡當作下個基地台的起點 ---- $O(N(\log{N}+\log{(\max{P_i})}))$ ```cpp= #include<bits/stdc++.h> #define fastio ios::sync_with_stdio(0); cin.tie(0); using namespace std; int n, k, p[50005]; bool check(int len){ int cnt=1, r=p[0]+len; // cnt: 基地台數，r: 現在基地台右界 for(int i=0; i<n; i++){ if(p[i]<=r) continue; // 這個座標包含在上個基地台範圍內 else{ r=p[i]+len; // 把這個點當作新的左界，更新右界 cnt++; } } return cnt<=k; // 回傳是否可以設置 k 個以內 } int main(){ fastio cin >> n >> k; for(int i=0; i<n; i++) cin >> p[i]; sort(p, p+n); int l=0, r=1e9+5; // 座標最大 1e9 -> 長度最大 1e9 while(r-l>1){ // r 表示可以的長度 int m=(l+r)/2; if(check(m)) r=m; else l=m; } cout << r << '\n'; } ``` ---- 一些好用的函式 ```cpp lower_bound(begin_iter, end_iter, num); upper_bound(begin_iter, end_iter, num); ``` `lower_bound()` 可以找到序列中第一個大於等於 num 的指標 `upper_bound()` 可以找到序列中第一個大於 num 的指標 都是 $O(\log{n})$ 尋找 ---- ### [ABC 334 D - Reindeer and Sleigh](https://atcoder.jp/contests/abc334/tasks/abc334_d) 有 $N$ 個雪橇，第 $i$ 個雪橇需要 $R_i$ 隻馴鹿才能拉動 有 $Q$ 筆詢問，每筆詢問給定一個 $X$ 問你當有 $X$ 隻馴鹿時可以拉動幾個雪橇 ---- 雪橇的順序不影響我們選哪個 所以可以先按馴鹿需求量排序 每個雪橇需求量越少可以拉越多雪橇 也就是從需求量少的開始選 一定可以選到最多雪橇 ---- 把排序好的序列做前綴和再二分搜就好了！ `upper_bound()` 可以找到大於 $X$ 的第一個位置 這個位置減去最前面的位置 就是小於等於 $X$ 的序列長度 也就是我們要的答案！ ---- $O((N+Q)\log{N})$ ```cpp= #include<bits/stdc++.h> #define fastio ios::sync_with_stdio(0); cin.tie(0); using namespace std; int n, q, arr[200005]; long long pre[200005]; int main(){ fastio cin >> n >> q; for(int i=0; i<n; i++) cin >> arr[i]; sort(arr, arr+n); pre[0]=arr[0]; for(int i=1; i<n; i++) pre[i]=pre[i-1]+arr[i]; // 前綴和 for(int i=0; i<q; i++){ long long x; cin >> x; cout << upper_bound(pre, pre+n, x)-pre << '\n'; } } ``` --- ## 三分搜 ---- 現在給你一個上凹函數 請你求出他的最小值  ---- 一樣開始有一個區間讓我們搜尋 每次可以平分成三塊 有兩個切點 $lmid, rmid$ 如果 $f(lmid)<f(rmid)$ 那麼答案就會在 $[l, rmid]$，反之亦然  ---- 怎麼判斷要什麼時候結束搜尋？ 可以設定一個 $eps$ 表示很小的數 當 $r-l<eps$ 的時候就結束 另一種方法就是跑固定次數就停止 ---- 浮點數三分搜 ```cpp= double l, r; for(int i=0; i<100; i++){ double lm=(2*l+r)/3; double rm=(l+2*r)/3; if(f(lm)<f(rm)) r=rm; else l=lm; } ``` ---- 三分搜在 APCS 或競賽裡比較少見 主要是處理一些凹函數找極值的問題