---
title: C++教室第九節社課
slideOptions: # 簡報相關的設定
theme: blood # 顏色主題
transition: 'slide' # 換頁動畫
parallaxBackgroundImage: 'https://wallpapercave.com/wp/wp2533041.jpg '
---
C++第九節社課講義
===
>[name=Derek] [time= April 9 ] [color=#333]
###### tags:`tcirc` `社課`
----
[TOC]
---
## 分治(Divide & Conquer)
----
+ 又稱「 各個擊破法 」。把大問題切割成二或多個小問題， 再把小問題的解答組合成大問題的解答。
----
### 合併排序(Merge Sort)
----
+ Devide合併排序的這個算法是先將需要排序的陣列分為左右兩區塊，左右的每個區塊又分為更小的左右兩區
+ Conquer:遞迴完，切到不能再切之後，兩兩排序。
+ Combine:把每個子問題的答案一一比較後結合，得到排序完的解。
----
1. 分區
```cpp=
void merge_sort(int a[], int l,int r){
if(r - l <= 1) return; //遞迴終止條件
int m = (l+r)/2;
merge_sort(a, l, m); //左分區
merge_sort(a, m, r); //右分區
combine(a,l,m,r); //合併左右
}
```
----
2.排序並結合
```cpp=
//i是左區的index(l ~ (m-1))
//j是右區的index(m ~ (r-1))
void combine(int a[],int l,int m,int r){
int tmp[r - l], j=m, k=0; //tmp紀錄新狀態
for(int i=l;i<m;i++){
while(j < r && a[i] > a[j]){ //這裡會決定遞增、遞減
tmp[k++] = a[j++]; //先放進去之後數字才+1喔
}
tmp[k++] = a[i];
}
for(k = l;k<j;k++){ //用tmp更新(只要更新到j就好)
a[k] = tmp[k - l];
}
return;
}
```
----
{%youtube ZRPoEKHXTJg %}
----
+ 複雜度:
merge的動作是$O(n)$
遞迴深度是$O(logn)$，，由於每層遞迴的長度總和都是$n$，所以整體複雜度$O(nlogn)$。
----
+ vector or array
剛剛的merge_sort引數是放array，但如果要用vector的話記得要傳參照(&)，因為array本身就是記憶體的位置，用vector寫的話某些地方的index要特別注意喔。
----
#### [d064: P-5-4. 反序數量 (APCS201806)](https://judge.tcirc.tw/ShowProblem?problemid=d064)
mergesort 會了這題就可以寫摟。
----
### [d065: P-5-7. 大樓外牆廣告](https://judge.tcirc.tw/ShowProblem?problemid=d065)
----
#### 天真的寫法:
在每段中都取最小樓高做長方形的高，所以複雜度......$O(n^3)$!
----
#### 找找看面積怎麼算
找到一段範圍之中的最小高度，這時候的面積就會是該段長度乘上最小的那個高度。
----
#### 分治的概念:
重點來了，這時候最小高度的座右兩邊區域，因為他是最小高度的關係，左右兩區域的面積必定不會跨過最小的這段高度，所以我們可以遞迴往下繼續找解了，耶。
----
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
ll h[N];
ll solve(int l, int r) {
if (l>=r) return 0;
if (l+1==r) return h[l];
int m=min_element(h+l, h+r) - h;
ll ans=(r-l)*h[m];
ans=max(ans, solve(l,m));
ans=max(ans, solve(m+1,r));
return ans;
}
int main() {
int n;
cin >> n;
for (int i=0;i<n;i++)
cin >> h[i];
cout << solve(0,n);
}
```
----
#### 蛤，怎麼爆了。
看看複雜度，如果每次的最小高度都在邊邊的話，這樣就是$O(n^2)$餒。
----
#### 回頭再想一次分治
其實我們並不用特意去找最小的點，每次一樣找中間點$m = {(l+r)\over2}$，然後左右下去遞迴。
----
#### 那如果要找的範圍越過中點怎麼辦
這個問題很奇妙，因為左邊跟右邊下去遞迴，所以只要考慮有過中點的那個區塊就OK了。接著往左邊跟右邊做延伸，如果左右高度比目前高度還要大那就把邊界+1，如果左右高度比目前高度小那就更新目前高度到左右邊高的那個（在兩者都小於中間時取較高的那一個）
----
#### 應該不會爆了
合併時往左右跑最多只有$n$個，複雜度是$O(n)$。
遞迴深度是$O(logn)$，，由於每層遞迴的長度總和都是$n$，所以整體$O(nlogn)$。
----
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
int h[N];
long solve(int l,int r){
if(l+1==r) return h[l];
if(l>=r) return 0;
int m=(l+r)/2;
ll ansL=solve(l,m);
ll ansR=solve(m+1,r);
ll ans=max(ansL,ansR);
ll nowH=h[m];
int pL=m-1;
int pR=m+1;
while(l<=pL or pR<=r){
while(l<=pL and h[pL]>=nowH) pL-=1;
while(pR<=r and h[pR]>=nowH) pR+=1;
ans=max(ans,nowH*(pR-pL-1));
nowH=(pR>r or (l<=pL and h[pL]>=h[pR]))? h[pL]: h[pR];
}
return ans;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>h[i];
cout<< solve(0,n) <<'\n';
}
```
---
## 二分搜尋法(Binary Search)
----
對於某些題目，我們時常需要尋找某些符合特定條件的值，並且有時候會希望他盡量最小/最大。
我們可以使用最簡單的演算法：線性搜尋法(Linear Search)。
其實就是單層的列舉所有可能的元素並且選出我們所要的。
不過當我們想找的資料具有一定的有序性，我們是否能對線性搜尋作優化呢?
----
來思考一個簡單的問題：
有一個陣列A及數字K，判斷K在A的哪個位置。
線性搜尋法：
```cpp=
int pos(int A[],int k){
for(int a = 0;a < n;a++){
if (A[a] == k) return a;
}
}
```
很簡單。複雜度是$O(n)$。
----
那如果A是**排序過**的陣列呢?
能否對線性搜尋再進行優化呢?
----
由於A是排序過的陣列，所以如果一個元素A[i] < K，
那表示A[0~i] < K 都成立，當然，這些數字更不可能等於K了。
如果一個元素A[i] > K，那表示A[i~n-1] > K 都成立，而這些數字也不會等於K。
既然那些數字都不可能等於K，那幹嘛去找呢?
這樣似乎省了不少工夫，沒錯吧?
重點是我們要怎麼謹慎挑選i，讓我們省下最多功夫呢?
----
如果我們i挑選最中間的元素，那麼無論如何都可以「捨去」一半的數字。
於是我們再對剩下的元素作同樣的動作，也就是說每次剩餘元素會是原本的一半。
所以我們的複雜度就是.....
$O(logn)$！
這樣的複雜度實際上已經足夠快了(雖然這個方法不見得是最好的)。
----
#### 遞迴做法
```cpp=
//表示剩餘元素是A[l~r]
int search(int A[],int l,int r,int k){
int mid = (l+r)/2;
if (A[mid] < k) return search(A,l,mid-1,k);
else if (A[mid] > k) search(A,mid+1,r,k);
else return mid;
}
```
----
#### 迴圈作法
```cpp=
//表示剩餘元素是A[l~r]
int search(int A[],int k){
int l = 0,r = n;
while(l <= r){
int mid = (l+r)/2;
if (A[mid] < k) l = mid+1;
else if (A[mid] > k) r = mid-1;
else return mid;
}
}
```
----
### 二分搜尋應用
題目：[b063: 區間查詢 level 1](https://judge.tcirc.tw/ShowProblem?problemid=b063)
有一個整數陣列A，有Q筆詢問。
每一筆詢問有兩個整數X,Y。
請輸出A中位於[X,Y]區間的數共有多少個。
----
簡單作法：
每次都數過一遍，複雜度$O(NQ)$，顯然不行。
----
#### sort()
我們先想辦法將A排序，可以使用sort函數。
用法
```cpp=
#include<algorithm> //here
sort(s,s+n); //by pointer
sort(v.begin(),v.end()); //by iterator
```
所以只要一行：
```cpp=
sort(A,A+n);
```
這個函式所用的演算法時間複雜度是$O(nlogn)$
----
#### 思考模式
我們將問題拆成兩部分：
1. 找出A中不小於X的最左邊的數
2. 找出A中不大於Y的最右邊的數
3. 將兩個位置相減就好了~
----
用我們之前的想法，如果某個數K < X，表示我們可以捨棄掉K左邊(含K)的所有數字。因為他們都不符合條件。
而若K >= X，我們可以捨去K右邊(不含K)的所有數。因為K符合條件，所以答案一定在K的左邊或是K本身。
----
問題是...怎麼結束呢?
我們之前介紹的二分搜尋保證K一定會存在，所以找到K就是結束了。
可是大部分的題目都不是這樣，我們必須知道我們甚麼時候才是找到答案了，還有答案是多少。
----
### 二分搜尋的多種流派
----
#### 閉區間派
```cpp=
int l = -1,r = n;
while(l+1 < r){
int mid = (l+r)/2;
if (s[mid] >= x) r = mid;
else l = mid;
}
// l = r-1
```
可以發現區間會不斷縮小直到r-l=1(此時mid = l)，所以這個時候退出。
那答案是誰呢?
首先如果我們設-1、n為無限大/無限小。
你可以發現：不論何時都會滿足 s[l] < x，s[r] >= x，此時的答案是r。
所以答案就是r!
至於什麼超出陣列範圍的東東不須擔心!因為那兩個點根本不可能碰到。
(不過答案有可能是n，在X > s[n-1]時)
----
#### 左閉右開派
```cpp=
int l = 0,r = n;
while(l < r){
int mid = (l+r)/2;
if (s[mid] >= x) r = mid;
else l = mid+1;
}
```
可以發現區間會縮小到r=l，這個時候就可以退出。
答案是誰呢?
一樣設n是無限大，此時的s[r] >= x一定成立。
所以顯然答案是r!
----
#### 開區間派
```cpp=
int l = 0,r = n-1;
while(l <= r){
int mid = (l+r)/2;
if (s[mid] >= x) r = mid-1;
else l = mid+1;
}
```
區間一直縮小直到r = l-1，在這個時候退出很合理。
答案是多少呢?
考慮我們要的答案ans是最左邊 >= X的位置，不就表示s[ans-1] < X嗎?
那答案很明顯了吧?就是l!
----
選擇一個流派，之後盡量用同種寫法，自己不易搞混，寫起來更輕鬆。
(btw 我是開區間派)
好...剩下的部分交給你們囉~
----
#### 二分搜尋的使用時機
通常遇到這種「在區間/陣列A中滿足某條件的最小/大數值X」，如果資料存在單調性，也就是當X滿足條件，X+1(或X-1)也會滿足條件，就可以用二分搜尋快速解決。
複雜度是$O(logn)$
----
### 對答案二分搜
題目：[d049: P-4-9. 基地台 (APCS201703)](https://judge.tcirc.tw/ShowProblem?problemid=d049)
直線上有 N 個要服務的點，每架設一座基地台可以涵蓋直徑 R 範圍以內的服務點。輸
入服務點的座標位置以及一個正整數 K，請問：在架設 K 座基地台以及每個基地台的
直徑皆相同的條件下，基地台最小直徑 R 為多少？
----
如範例測資一的圖如下：
可以看出
K = 1時：R = 7(基地台位置：4.5)
K = 2時：R = 3(基地台位置：2,6.5)
K = 3時：R = 1(基地台位置：1.5,5,7.5)
----
乍看之下不好下手，但是如果我們思考另一個很像的問題：
給定直徑R，最少架設幾座基地台才能覆蓋所有服務點?
----
考慮所有服務點中最左邊的點L，如果有一個基地台覆蓋到L左邊的其他點，那麼我們為何不把基地台右移一點呢?因為L左邊已經沒有其他服務點了，把基地台右移不但不會有損失，還有機會覆蓋到右邊的服務點。
所以我們可以確定最左邊的基地台的左界一定會切到L點。
然後我們忽略所有已經被覆蓋的點後，再對剩下的點作重複的動作。
於是我們就解出了在**R確定的情況下最小的K值**。
----
回到原來的問題，我們希望找出給定K時最小的R值。
想一想，我們找到的這個R值，他對應的最小K值有甚麼限制呢?
當然，如果這個R值的最小K值比K大，那顯然不合理，所以我們對R的限制就是**最小K值不超過K**
----
再想一想，你有沒有發現當R越大時，他的最小K值會越小呢?
所以如果R的最小K值 > K，所有r > R的最小K值都 > K...
這不就是二分搜嗎?
所以我們只要對R二分搜，找出最小K值 <= K的最小R值就好囉！
----
這個技巧叫做對答案二分搜，複雜度也是$O(logn)$。
最終的複雜度就是$O(nlogn)$
----
#### 更多有關二分搜的事...
[codeforces EDU](https://codeforces.com/edu/course/2/lesson/6)
codeforces是一個國際的online judge網站，有非常大量的題目及資源。
在CF上註冊帳號後，便可以參加CF定期舉辦的線上比賽，你的成績最後會加在你的積分(Rating)
上。CF EDU則是一系列教各種不同演算法的課程，其中二分搜的單元內容詳盡而且難度適中，如果有興趣可以聽聽看。
---
## 補充
---
### 分析二分搜尋法
回到前面的問題：
有一個陣列A及數字K，判斷K在A的哪個位置。
如果假設搜尋任何元素的成本都一樣，並且每個元素被選作K的機率相等。
請證明二分搜尋法的效率最高。
----
我們無法事先知道K的值，所以不可能找到最好的i，但是我們可以嘗試把期望值降到最低。
假設我們今天找A[i]和K比較，那麼我們來算算我們「捨去」掉的元素的期望值是多少。
對於比較結果，有三種可能：
1. A[i] = K。找到了，所以不須再找了。
2. A[i] < K。捨棄0~i的元素，從剩下的繼續找。
3. A[i] > K。捨棄i~n-1的元素，從剩下的繼續找。
----
$E = \frac{1}{n}*(n) + \frac{i}{n}*(i+1) + \frac{n-1-i}{n}*(n-i)$
$= 1 + \frac{i^2+i+(n-i)^2-(n-i)}{n}$
$= 1 + \frac{2i^2-2ni+n^2+2i-n}{n}$
$= n + \frac{2i^2-2ni+2i}{n}$
所以要最大化E，$i = \frac{2n-2}{4} = \frac{n-1}{2}$
---
### 排序演算法
----
#### 泡沫排序
掃描過整個陣列，若兩個相鄰元素順序相反了就把他們對調。
依照這個算法可以發現：最大的元素會在第一次「浮」到最高層，這也就是他的名字由來。
所以，只要對陣列掃過n-1次，所有元素都會被排序好。
複雜度：$O(n^2)$
----
```cpp=
for(int a = 0;a < n;a++){
for(int b = 1;b < n-a;b++){
if (s[b-1] > s[b]) swap(s[b],s[b-1]);
}
}
```
----
#### 選擇排序
每次找陣列裡的最小值，放到最前面，然後再找。
複雜度：$O(n^2)$
----
```cpp=
for(int a = 0;a < n;a++){
int mn = a;
for(int b = a;b < n;b++){
if (s[b] < s[mn]) mn = b;
}
swap(s[mn],s[a]);
}
```
----
#### 插入排序
由前而後掃描陣列，將新的元素插入到舊的陣列中。
由於前面的陣列已經排完了，所以將新元素插入到剛好小於他的位置前面就好(很像泡泡排序)
複雜度：$O(n^2)$
----
```cpp=
for(int a = 0;a < n;a++){
int i = a;
while(i != 0&&s[i-1] > s[i]){
swap(s[i],s[i-1]);
i--;
}
}
```
----
#### 快速排序
每次選一個點X當作參考點，將小於X的放到X的左邊，其他放到X的右邊，然後遞迴兩邊。
平均情況複雜度是$O(nlogn)$，但是如果每次的參考點都在邊緣，有可能退化成$O(n^2)$。
所以實作上有時候會隨機選點。
----
```cpp=
//無隨機選點(以最左邊為參考點)
void qsort(int s[],int l,int r){
if (l >= r) return;
int i = l+1,j = r;
int x = s[l];
while(i != j){
if (s[j] > x) j--;
else if (s[i] < x) i++;
else swap(s[i],s[j]);
}
if (s[i] < x){
swap(s[i],s[l]);
qsort(s,l,i-1);
qsort(s,i+1,r);
}
else{
swap(s[i-1],s[l]);
qsort(s,l,i-2);
qsort(s,i,r);
}
}
```
----
#### 基數排序
先以較低位排序，再以較高位排序。
排序的過程需保證「穩定」(stable)，也就是說當兩個數比較值一樣時原本的順序不會改變。
也就是說如果X跟Y在某位數是一樣的，那麼X跟Y的順序就會跟他們之前排的順序一樣(就是比之前的結果)
複雜度:$O(nk)$，k是數字中最多位的位數。
----
```cpp=
vector<int> v[10];
vector<int> s;
for(int a = 0;a < k;a++){
for(int b = 0;b < n;b++){
v[(s[b]/((int)pow(10,a)))%10].push_back(s[b]);
}
s.clear();
for(int c = 0;c < 10;c++){
for(int d = 0;d < v[c].size();d++) s.push_back(v[c][d]);
v[c].clear();
}
}
```
Sign in with Wallet
Connect another wallet