changed 5 years ago  
Linked with GitHub

搜尋與排序

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









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 版













struct Comp{
    bool operator()(T a, T b){
        return /*...*/;
    }
};

//...

vector<T> a;
sort(a.begin(), a.end(), Comp());

set<T, Comp> s;

function 版









bool comp(T a, T b){
    return /*...*/;
}

//...

vector<T> a;
sort(a.begin(), a.end(), comp);

lambda 版

vector<T> a;
sort(a.begin(), a.end(), [](T a, T b){return /*...*/;});

搜尋

二分搜尋法

猜數字？

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\)
保證有解

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

有 \(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)\)
求頂點









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 裡的排序

sort(l, r, comp)

氣泡排序

分成已排序部分和未排序部分

一開始整個序列都是未排序的

找到未排序部分裡最大的元素
移到未排序部分的尾端

實作方式

第一個元素和第二個元素比較
第一個元素比較大就交換
第二個元素和第三個比較
如果第二個比較大就交換…… 未排序部分的倒數第二個元素和倒數第一個元素比較
倒數第二個比較大就交換

然後最後一個元素會加入已排序部分
未排序部分的大小少 1
接著重複一樣的動作
直到排序完為止









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
然後重複一樣的動作

實作方式

暴力

















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)\)
再把兩邊合併

























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
比它小的元素都放到它左邊
比它大的元素都放到它右邊

兩側遞迴排序


























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，讓每個元素長不一樣

基數排序

非比較排序

從數字最低位開始看
拿十個桶子
最低位是幾就放第幾個桶子

從編號小的桶子開始依序拿出
放回序列
序列會按最低位排序

看次低位
也拿十個桶子
這一位是幾就放第幾個桶子
序列會按次低位排序，相同的按最低位

一直往高位看



















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

有 \(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)\) 排序

#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;
}
Select a repo