# 搜尋與排序 Wiwi Ho ###### tags: `CRC` --- https://hackmd.io/@wiwiho/crc1082algo https://tg.pe/xgaG  --- # 比大小 --- ## 怎麼比大小 ---- ## 全序關係 ---- 記作 $\leq$ 就是常見的比較符號 ---- 但意義不一定是平常說的小於等於 這裡的 $\leq$ 就純粹是一種符號 沒有固定的意義 ---- 某集合 $X$ 滿足全序關係的條件： - $\forall a,b \in X, a \leq b \land b \leq a \Rightarrow a = b$ - $\forall a,b,c \in X, a \leq b \land b \leq c \Rightarrow a \leq c$ - $\forall a,b \in X, a \leq b \lor b \leq a$ ---- 也就是說，$X$ 內的每一對元素要可以互相比較 ---- ## 非嚴格全序 ---- 記作 $<$ 就是 $\leq$ 少 $=$ ---- 性質： - $\forall a,b,c \in X, a < b \land b < c \Rightarrow a < c$ - $\forall a,b \in X, a < b \lor b < a \lor a = b$ ---- ## 偏序關係 ---- 也記為 $\leq$ ---- 性質： - $\forall x \in X, x \leq x$ - $\forall a,b \in X, a \leq b \land b \leq a \Rightarrow a = b$ - $\forall a,b,c \in X, a\leq b \land b \leq c \Rightarrow a \leq c$ ---- 和全序的差別是 偏序關係不需要每一對元素都能互相比較 ---- ## 單調性 ---- 函數 $f: X \to Y$ ---- 非嚴格遞增 $\forall x_1,x_2 \in X \land x_1 \leq x_2, f(x_1) \leq f(x_2)$ ---- 嚴格遞增 $\forall x_1,x_2 \in X \land x_1 \leq x_2, f(x_1) < f(x_2)$ ---- 非嚴格遞減 $\forall x_1,x_2 \in X \land x_1 \leq x_2, f(x_1) \geq f(x_2)$ ---- 嚴格遞減 $\forall x_1,x_2 \in X \land x_1 \leq x_2, f(x_1) > f(x_2)$ --- ## Comparator ---- 用來定義比較方式的 function 放在跟比較有關的 function 的參數 和 container 的 template ---- ```cpp= vector<int> a; sort(a.begin(), a.end()); //把 a 裡的東西由小到大排序 sort(a.begin(), a.end(), less<>()); //把 a 裡的東西由小到大排序 sort(a.begin(), a.end(), greater<>()); //把 a 裡的東西由大到小排序 set<int> s1; //s1 裡的東西會由小到大排序 set<int, less<>> s2; //s2 裡的東西會由小到大排序 set<int, greater<>> s3; //s3 裡的東西會由大到小排序 ``` ---- ## less<>、greater<> STL 提供的 comparator 表示使用 $<$ 和 $>$ 運算子 ---- ## 自己實作 ---- struct 版 ```cpp= struct Comp{ bool operator()(T a, T b){ return /*...*/; } }; //... vector<T> a; sort(a.begin(), a.end(), Comp()); set<T, Comp> s; ``` ---- function 版 ```cpp= bool comp(T a, T b){ return /*...*/; } //... vector<T> a; sort(a.begin(), a.end(), comp); ``` ---- lambda 版 ```cpp vector<T> a; sort(a.begin(), a.end(), [](T a, T b){return /*...*/;}); ``` --- # 搜尋 --- ## 二分搜尋法 ---- 猜數字？ ---- ```cpp int l = /*初始下界*/, r = /*初始上界*/; while(l < r){ int m = (l + r) / 2; if(check(m)) //變更邊界 else //變更邊界 } ``` ---- 變更邊界 - $l=m$ - $r=m$ - $l=m+1$ - $r=m-1$ ---- 怎麼選 $m$ 如果有狀況會把 $l$ 變更成 $m$ 當 $l+1=r$ 時，$m=\lfloor\frac{2l+1}{2}\rfloor=l$ 範圍會卡住 改成 $m=\lfloor\frac{l+r+1}{2}\rfloor$ ---- ## 範例 ---- 給遞增數列 $a_1 \leq a_2 \leq a_3 \leq ... \leq a_n$ 和數字 $x$ 求最小的 $i$ 滿足 $a_i \geq x$ 保證有解 ---- ```cpp vector<int> a(n); int x; //... int l = 0, r = n - 1; while(l < r){ int m = (l + r) / 2; if(a[m] >= x) r = m; else l = m + 1; } ``` ---- ## 時間複雜度 ---- 每次範圍大小變為本來的約一半 $\Rightarrow$ 時間複雜度 $O(\log_2 n)=O(\log n)$ ---- ## 對答案二分搜 ---- [ZeroJudge c575](https://zerojudge.tw/ShowProblem?problemid=c575) 有 $N$ 個服務點 你最多可以放 $K$ 個基地台 並決定一個盡量小的半徑 $R$ 使每一個服務點都有一個距離它至多 $R$ 的基地台 求最小的 $2R$ ---- 如果 $R=x$ 時可以找到放基地台的方法 那 $R>x$ 時也可以 $\Rightarrow$ 二分搜最小的可以找到怎麼放基地台的 $R$ ---- 怎麼找？ 盡量把基地台往後放 ---- ## STL 裡的二分搜 ---- lower_bound(l, r, n, comp) 回傳 $[l,r)$ 中第一個不小於 $n$（由 comp 定義）的元素位置 ---- upper_bound(l, r, n, comp) 回傳 $[l,r)$ 中第一個大於 $n$（由 comp 定義小於）的元素位置 --- ## 三分搜尋法 ---- 二分搜：把範圍分兩段 三分搜：把範圍分三段 ---- 分隔點  ---- ## 範例 ---- 有一開口向上的二次函數 $f(x)$ 求頂點 ---- ```cpp= double l = -1e9, r = 1e9; while(r - l > 1e-4){ double m1 = (2 * l + r) / 3; double m2 = (l + 2 * r) / 3; if(f(m1) < f(m2)) r = m2; else l = m1; } cout << l << " " << r << "\n"; ``` --- # 排序 --- ## STL 裡的排序 ```cpp sort(l, r, comp) ``` --- ## 氣泡排序 ---- 分成已排序部分和未排序部分 ---- 一開始整個序列都是未排序的 ---- 找到未排序部分裡最大的元素 移到未排序部分的尾端 ---- 實作方式 第一個元素和第二個元素比較 第一個元素比較大就交換 第二個元素和第三個比較 如果第二個比較大就交換…… 未排序部分的倒數第二個元素和倒數第一個元素比較 倒數第二個比較大就交換 ---- 然後最後一個元素會加入已排序部分 未排序部分的大小少 1 接著重複一樣的動作 直到排序完為止 ---- ```cpp= vector<int> a(n); //... for(int i = 0; i < n - 1; i++){ for(int j = 0; j < n - i - 1; j++){ if(a[j] > a[j + 1]) swap(a[j], a[j + 1]); } } ``` ---- 複雜度 $O(n^2)$ --- ## 插入排序 ---- 同樣分成已排序部分和未排序部分 但通常未排序部分會放前面 ---- 在未排序部分裡找隨便一個數字 再找到它應該放在已排序部分的哪裡 然後塞進去 未排序部分大小會少 1 然後重複一樣的動作 ---- 實作方式 暴力 ---- ```cpp= vector<int> a(n); //... for(int i = 1; i < n; i++){ int pos = i; for(int j = i + 1; j < n; j++){ if(a[j] < a[pos]) pos = j; } int p; for(p = 0; p < i; p++){ if(a[p] > a[pos]) break; } int t = a[pos]; for(int j = pos; j > p; j--) a[j] = a[j - 1]; a[p] = t; } ``` ---- 時間複雜度 $O(n^2)$ --- ## 合併排序 ---- 把序列切兩半 分別排序過後再合併 =某種遞迴 ---- $\text{mergesort}(l,r)$： 將 $[l,r]$ 範圍排序 $m=\frac{l+r}{2}$ 呼叫 $\text{mergesort}(l,m)$ 和 $\text{mergesort}(m + 1, r)$ 再把兩邊合併 ---- ```cpp= void mergesort(vector<int>& a, int l, int r){ if(l == r) return; int m = (l + r) / 2; mergesort(a, l, m); mergesort(a, m + 1, r); vector<int> b; int lp = l, rp = m + 1; while(lp <= m && rp <= r){ if(a[lp] <= a[rp]) b.eb(a[lp]), lp++; else b.eb(a[rp]), rp++; } while(lp <= m) b.eb(a[lp]), lp++; while(rp <= r) b.eb(a[rp]), rp++; for(int i = 0; i < r - l + 1; i++) a[l + i] = b[i]; } //... vector<int> a(n); //... mergesort(a, 0, n - 1); ``` ---- 時間複雜度 ---- 遞迴到相同深度的 範圍不會重疊 且聯集是整個序列 ---- 遞迴深度 每遞迴一層 範圍大小會少約一半 $O(\log n)$ ----  ---- $O(n \log n)$ --- ## 快速排序 ---- 和合併排序相似 把範圍分兩邊分別排序 但不是直接切中間 ---- 選一個元素當 pivot 比它小的元素都放到它左邊 比它大的元素都放到它右邊 兩側遞迴排序 ---- ```cpp= void quicksort(vector<int>& a, int l, int r){ if(l >= r) return; int pv = /*...*/; swap(a[pv], a[r]); int lp = l, rp = r - 1; while(lp < rp){ while(lp < rp && a[lp] <= a[r]) lp++; while(lp < rp && a[rp] > a[r]) rp--; swap(a[lp], a[rp]); } if(a[rp] <= a[r]) rp = r; swap(a[rp], a[r]); quicksort(a, l, rp - 1); quicksort(a, rp + 1, r); } //... vector<int> a(n); //... quicksort(a, 0, n - 1); ``` ---- 複雜度 ---- 遞迴到一樣深度的 範圍不重疊 聯集也是整個序列 $\Rightarrow$ 複雜度是 遞迴深度 $\times O(n)$ ---- 遞迴深度？ 和遞迴一層，範圍如何改變有關 ---- 如果每次範圍少 1 深度就是 $O(n)$ ---- 如何選 pivot？ 選定點：很好構出每次範圍少 1 的 case Random! ---- 有 $\frac{1}{2}$ 機率選到中間 50% 的元素 i.e. 比它小至少 25%、比它大至少 25% 範圍最多變 $\frac{3}{4}$ ---- 要選到最多 $\log_{\frac{4}{3}} n=\frac{log_2 n}{log_2 \frac{4}{3}} \approx 2.409 \log_2 n$ 次滿足條件的 pivot ---- 選到的機率是 $\frac{1}{2}$ $\Rightarrow$ 約 $2 \times 2.409 \log_2 n$ 次就可選到 $2.409 \log_2 n$ 次 遞迴深度 $=O(2 \times 2.409 \log_2 n)=O(\log n)$ 複雜度 $O(n \log n)$ ---- 如果沒有這樣的元素能當 pivot？ ---- 如果幾乎所有元素都一樣 那和 pivot 一樣的元素一定會被丟到同一邊 $\Rightarrow$ 變 $O(n^2)$ ---- 解決方法 換成 pair，讓每個元素長不一樣 --- ## 基數排序 ---- 非比較排序 ---- 從數字最低位開始看 拿十個桶子 最低位是幾就放第幾個桶子 ---- 從編號小的桶子開始依序拿出 放回序列 序列會按最低位排序 ---- 看次低位 也拿十個桶子 這一位是幾就放第幾個桶子 序列會按次低位排序，相同的按最低位 ---- 一直往高位看 ---- ```cpp= vector<int> a; //... vector<pair<int, int>> t(a.size()); for(int i = 0; i < a.size(); i++) t[i] = make_pair(a[i], a[i]); while(max_element(t.begin(), t.end())->F > 0){ vector<vector<pair<int, int>>> b(10); for(auto i : t) b[i.F % 10].emplace_back(i); t.clear(); for(int i = 0; i < 10; i++){ for(auto j : b[i]){ t.emplace_back(make_pair(j.first / 10, j.second)); } } } for(int i = 0; i < a.size(); i++) a[i] = t[i].S; ``` ---- 複雜度 ---- 令 $x=2^{63}-1=$ long long 最大值 會看 $log_{10} x$ 位，$O(\log_{10} x)$ 看每一位時 掃 $10+1$ 次數列，算作 $O(10n)$ 總複雜度 $O(10n \log_{10} x)=O(n)$？ ---- 常數 $10 \log_{10} x \approx 190$ ---- 用別的底？ $O(bn \log_b x)$ 常數：$b \log_b x$ ---- 不管怎樣都很大 --- ## 例題 ---- [ZeroJudge c471](https://zerojudge.tw/ShowProblem?problemid=c471) 有 $N$ 個物品 你必須把它們疊起來 成本是 $\sum_{i=1}^N f(i) \times \sum_{j=\text{所有在它上面的東西} w(j)}$ 最小化成本 ---- 只有兩個物品時 如果 1 在 2 上方 成本：$w(1) \times f(2)$ 如果 2 在 1 上方 成本：$w(2) \times f(1)$ ---- 如果 $w(1) \times f(2) < w(2) \times f(1)$ 1 就要在 2 上面 移項 $\frac{w(1)}{f(1)} < \frac{w(2)}{f(2)}$ 某種全序關係？ ---- 在一種堆疊順序中 相鄰的兩個物品交換 和其他物品相對位置不變 所以對成本的改變只和它們有關 ---- 如果 $i$ 在上 $j$ 在下 若 $\frac{w(i)}{f(i)} > \frac{w(j)}{f(j)}$ 把它們交換後成本會變小 ---- 按 $w(i) \times f(j) < w(j) \times f(i)$ 排序 ---- ```cpp #include <bits/stdc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); typedef long long ll; using namespace std; vector<ll> f, w; bool comp(int i, int j){ return w[i] * f[j] < w[j] * f[i]; } int main(){ StarBurstStream int n; cin >> n; f.resize(n); w.resize(n); for(int i = 0; i < n; i++) cin >> w[i]; for(int i = 0; i < n; i++) cin >> f[i]; vector<int> a(n); for(int i = 0; i < n; i++) a[i] = i; sort(a.begin(), a.end(), comp); ll ans = 0; ll sum = 0; for(int i = 0; i < n; i++){ ans += sum * f[a[i]]; sum += w[a[i]]; } cout << ans << "\n"; return 0; } ```