owned this note   changed 4 months ago  
Published Linked with GitHub

search algorithm & 實作misc

Introduction to Competitive Programming

  • 二分搜
  • 三分搜
  • 實作misc

二分搜

讓搜尋的範圍減少一半的方式

例題：

給一長度為 \(n\) 的已排序陣列 \(a\)，以及 \(m\) 個詢問，問你 \(x\) 是否在 \(a\) 之中。

做法一：

每次遍歷過整個陣列看 \(x\) 是否在 \(a\) 之中
複雜度：\(O(n)\)

做法二：

可以用陣列已排序的性質，二分搜陣列。

可以觀察到如果一個數字 \(d\) 在陣列中比 \(x\) 小， \(x\) 如果有出現在陣列中，就一定在 \(d\) 的右邊。
如果善用這個性質，每次就可以將搜索區間減少一半。

下面我們示範一下
在 \([1, 3, 5, 7, 9, 11, 13, 15, 17, 19]\) 上詢問 \(15\) 是否在陣列內

做法二：

一開始整個陣列都是有可能的範圍，所以

int l = 1, r = 10;

做法二：

看中間的位置是不是我們要的答案

int mid = (l + r) / 2; // mid = 5

做法二：

發現不是而且發現 \(arr[mid]\) 小於等於 \(15\)，所以左邊的區間不會有 \(15\)，因此我們將 \(left\) 移到 \(mid\) 的位置




if(arr[m] <= tar) {
	l = m;
}

做法二：

接下來就一樣，
看中間的位置是不是我們要的答案

做法二：

做法二：

找到答案了！

做法二：

雖然這個範例沒有出現，但如果 \(arr[mid]\) 大於 \(15\) 時，\(mid\) 的位置就不會是答案，因此我們會將 \(right\) 移到 \(mid - 1\) 的位置。




if(arr[mid] > tar) {
	right = mid - 1;
}

程式碼：















int l = 0, r = n - 1;
while(l < r) {
	int m = (l + r) / 2;
	if(arr[m] <= tar) {
		l = m;
	}
	else{
		r = m - 1;
	}
}
if(arr[l] == tar) {
	return 1;//有找到，在 l 的位置
}
return -1;//陣列沒有 tar 這個值

複雜度：

由於每次將區間切半，所以複雜度是 \(O(\log_2n)\)

二分搜的條件：

如果將已排序的陣列的 \(index\) 跟值進行映射 (\(x \rightarrow y\))，陣列就會變成單調遞增函數，二分搜就是在單調遞增的函數上進行搜尋。

例題：APCS 基地台

很常見的二分搜例題
題意：在數線上給定 \(n\) 個點，你可以在上面放 \(k\) 個基地台，每個基地台可以服務左右 \(\frac d 2\) 的範圍，詢問你 \(d\) 最少需要多少？ \(n, k, d\) 都是整數

先不管 \(k\) 的限制，可以觀察到 \(d\) 越小我們需要就需要越多的基地台，也就是 \(k\) 跟 \(d\) 成負相關，可以利用這個單調性來計算答案。

可以發現沒辦法直觀的利用 \(k\) 來找到 \(d\)，但如果有 \(d\) 時，計算 \(k\) 會相對簡單。

假設有五個點 \([1, 2, 5, 7, 8]\)， \(d\) 等於 \(5\) 時，要覆蓋到第一個點 \((1)\)，基地台最遠可以放到 \(3\) 的位置，而這個基地台最遠可以覆蓋到 \(5\) 的位置，因此沒被覆蓋到的點只剩 \(7、8\)，我們在剛好只能覆蓋到 \(7\) 的位置 \(9\) 放下基地台，基地台就可以覆蓋全部的點了！

範例程式碼：









int now = -1, d = 5, k = 0;
for(int i = 0; i < n; i++) {
	if(arr[i] > now) {
		k++;
		now = arr[i] + d;
	}
}
cout << k;

通過上面的程式碼，我們這樣可以花 \(O(n)\) 的時間找到 \(k\)，因此我們可以對 \(d\) 二分搜，找出最小的 \(d\) 會讓基地台的數量大於等於 \(k\)。

當搜出的數字比 \(k\) 小時，我們就需要將右界向左縮，因為 \(d\) 更大只會讓基地台的數量變少，相反的則是左界向右縮，只需要將二分搜跟上面的用 \(d\) 去尋找 \(k\) 的放在一起，就可以解出這題了。





















int check(int d){
    int now = -1, ans = 0;
    for(int i = 0; i < n; i++) {
        if(arr[i] > now) {
            now = arr[i] +  d;
            ans++;
        }
    }
    return ans;
}
signed main(){
    /*....*/
    while(l < r) {
        int mid = (l + r ) / 2;
        int ret = check(mid);
        if(ret <= k) r = mid;
        else         l = mid + 1;
    }
    /*....*/
}

細節：

在二分搜之前要確認搜的東西是有單調性 (遞增、遞減)

細節：

確定答案有在左界跟右界內，沒有的話就只是白做工。

細節：

可以發現根據題目的不同，左界跟右界的縮法會不太一樣

l = m, r = m - 1;
l = m + 1, r = m;
l = m + 1, r = m - 1;

二分搜的重點就是看出題目的性質，決定要怎麼去搜。

注意 二分搜並不能只使用單種習慣的方法，需要使用題目的性質來變化你縮的方法。

細節：

承接上頁，決定縮法之後，還要決定 mid 要怎麼求，當縮到最小的時候，有可能因為左右界縮法的問題，就陷入無限迴圈。
當 l=3, r=4, mid=(l+r)/2, l=m, r=m-1 時
如果二分搜的結果是縮左界的話 l \(\rightarrow\) mid，3 \(\rightarrow\)(3+4)/2=3，就會進入無限迴圈了！
這裡的解法是將 mid=(l+r+1)/2，也就是從向下取整改成向上取整。

三分搜

顧名思義，二分搜是將區間分成兩半，三分搜就是分成三半。
不過為什麼需要三分搜呢？
在什麼樣的情況下，分成兩份沒辦法解決問題，需要分成三份呢？

可以觀察到二分搜的條件 – 單調函數，像是在一次函數上找某一個值。
那如果是找二次函數的極值呢？

好像沒辦法簡單的依靠 mid 來求出區間要往哪邊縮，不過三分搜要怎麼求二次函數的極值呢？

雖然微分可以看出二分搜要往哪邊縮，但是如果是不是單純的二次函數，只是其中一邊單調遞減，其中一邊單調遞增，好像就沒辦法依靠對函數進行微分來求答案了

如果對以下函數找出極值，由於 f(ml) < f(mr) ，因此 ml 比 mr 離我們要的答案更近，所以我們會捨棄 [mr, r] 的區間，不過如果答案不在 [ml, mr] 之間呢？

可以觀察到在下圖的情況，我們一樣會捨棄掉 [mr, r] 的區間

只要根據誰的值離極值比較接近，我們就將另外一邊的區間捨棄掉，就可以三分搜出極值了！

實作程式碼











while(l < r) {
	int ml = l + (r - l) / 3;
	int mr = r - (r - l) / 3;
	if (check(ml) < check(mr)) {
		r = mr;	
	}
	else {
		l = ml;
	}
}

複雜度

每次切 \(\frac{1}{3}\) 的區間，複雜度 \(O(2 * \log_3n)\)

三分搜的條件：

如果函數內有水平線的話，除非答案在水平線上，不然就不能對她三分搜了，如下圖所示，沒辦法直接知道要捨棄哪一邊的區間

例題： vitos family

Vito 常拜訪親戚，所以想要找一間和所有親戚間總距離最小的房子住下來。輸入親戚數和門牌號，輸出最小距離和

對一個親戚來說，距離的公式是 \(d_i(x) = |s_i - x|\)，是一個單峰函數，而多個親戚的就是多個單峰函數的疊合，也是單峰函數，所以可以對 x 三分搜，找出單峰函數的極值。

複雜度 \(O(\log n)\)

然後再花 \(O(n)\) 時間計算最小距離和

總共 \(O(n)\)

\(f(x) = \sum\limits^n_{i = 1}|s_i - x|\)

可以發現任意兩個點 \(s_i\)、\(s_j\)，如果 \(s_i \le x \le s_j\)，\(d_i(x) + d_j(x) = |s_j - s_i|\)
所以對 f(x) 來說，只要對所有的 \(i、j\)，x 符合上述條件，f(x) 就會是最小的
而正好中位數符合這個條件，因此這題我們只要選擇中位數，再花 \(O(n)\) 的時間計算答案就可以解出來了

例題：最小包覆圓

平面上給 n 個點，在平面上任意位置畫一個圓，圓要包住所有的點，詢問半徑最少是多少

簡單化題目

平面上給 n 個點，在平面上 x = 0 上畫一個圓，圓要包住所有的點，詢問半徑最少是多少

再簡單一點

平面上給 1 個點，在平面上 x = 0 上畫一個圓，圓要包住所有的點，詢問半徑最少是多少

可以發現，對大圓來說，要覆蓋住一個點，半徑一定是點與線的最短距離，圓如果向上或是向下移動時，圓的半徑都要增加才能覆蓋住整個點，就會變成一個很典型的單峰函數。

回到前一題

可以發現在這題就變成多個單峰函數的疊合，而疊合後的單峰函數還會是單峰函數，因此我們就可以直接在 x = 0 上三分搜，搜出讓半徑最小的 y。
























struct node{
	double x, y;
}arr[n];

double check(double val) {
	double cmax = 0;
	for(int i = 0; i < n; i++) {
		cmax = max(cmax,(arr[i].x - 0) * (arr[i].x - 0) + 
                   (arr[i].y - val) * (arr[i].y - val));
	}
	return cmax;
}

while(r - l > eps) {
	double ml = l + (r - l) / 3;
	double mr = r - (r - l) / 3;
	if (check(ml) < check(mr)) {
		r = mr;	
	}
	else {
		l = ml;
	}
}

實作misc

I/O 優化

在C++中，加了這一行可以讓你的運行時間減少一半以上

ios::sync_with_stdio(0),cin.tie(0);

原理可以看這兒 \(\rightarrow\) link

以這題為例子

image

多筆測資

遇到多筆測資的時候，有些人可能會寫這樣

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        /*一筆測資要做的事情*/
    }
}

但後面題目可能會用到變數 i 和 t ， 加上多包一層括號會顯得很冗餘

因此可以考慮去呼叫函數，一筆測資就去呼叫一次函數

like this :

void solve(){
    //do i
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}

#define int long long

在一題當中，可能會用到很多變數，每個都要打 long long 的話 ， 太累了

只需要define這行就可以一次性把所有int變成long long，當然還有其他東西也可以這樣用。

不過需要記得把main函數的定義改掉，改成int32_t或是signed都可以

#define int long long
#define endl '\n'
#define pii pair<int,int>
#define x first
#define y second

#define int long long

int main(){} <----報錯
signed main(){} <-沒問題

全域變數定值宣告

同樣的，在一個題目你可能會用到很多次全域的陣列，而陣列可能是 2e5 的長度，所以你可能會打這樣

#include<bits/stdc++.h>
using namespace std;
int arr[200005],dp[200005],tmp[200005];
int main(){
    //do i
}

但是打那些數字很浪費時間所以可以…

const 是固定變數，你用const宣告出來的東西在之後就不能再更改，同時這樣開在全域就也不需要再函式間傳遞也不用考慮初始化的問題。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int arr[N],dp[N],tmp[N];
int main(){
    //do i
}

通常開陣列也會開大一丁點，避免取 index 取到外面

memset(arr,value,sizeof(arr))

時間複雜度是O(N)，可以把整個arr的值都變成value。好處是方便快速，但可賦值有限制 ex: -1 , 0 , 0x3f3f3f3f
同時要使用則要記得引入標頭檔cstring

#include<cstring>
signed main(){
    int arr[10];
    memset(arr,0,sizeof(arr));
    memset(arr,-1,sizeof(arr));
    memset(arr,0x3f3f3f3f,sizeof(arr));
}

for(auto i:arr)

可以快速遍歷陣列裡面的所有值，不用寫麻煩的 for(int i=…)

int main(){
    int arr[10]={0,1,5,2,4,5,1,22,1,0};
    for(auto i:arr){
        cout<<i<<" ";
    }
    
    vector<int>brr;
    for(int i=0;i<10;i++){
        brr.push_back(i);
    }
    for(auto i:brr){
        cout<<i<<" ";
    }
}

default code

在寫扣前，前面寫標頭檔好麻煩，有一個固定的模板可以開始寫會方便很多

IZhna's default code be like:

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define endl '\n'
#define pii pair<int,int>
#define Mikari_My_Wife ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
void solve(){
    //從這邊開始寫
}
signed main(){
    Mikari_My_Wife
    int t=1;
    //cin>>t
    while(t--){solve();}
}

酷東西 in VScode

沒跟到實體上課的人去看錄影檔

題單連結 https://vjudge.net/contest/670903

Select a repo