---
# System prepended metadata

title: MDCPP 外掛二分搜 + 模擬賽前總複習

---

# MDCPP 外掛二分搜 + 模擬賽前總複習

---

## 外掛二分搜

---

我覺得我上次講的那題有點太難了
所以我換了一題

---

直線上有 N 個要服務的點，每架設一座基地台可以涵蓋直徑 R 範圍以內的服務點。

輸入服務點的座標位置以及一個正整數 K，請問：在架設 K 座基地台以及每個基地台的直徑皆相同的條件下，基地台最小直徑 R 為多少

座標範圍不超過 1e9，1≤ K < N ≤ 5e4。

---

看到了 ! 這又是外掛二分搜的模型拉 ~
```給你一些條件，問你最少 / 最多要多少才能滿足條件```

---

我們又可以嘗試用外掛二分搜解決這個問題
我們可以嘗試二分搜基地台直徑 R

我們就能夠進行確認是否能覆蓋的測試

---

若能，就將二分範圍降至 左界 ~ mid-1
反之，就將二分範圍增至 mid+1 ~ 右界

---

那我們要怎麼確認呢 ?

---

我們紀錄一個變數 $lp$ 代表目前能夠達到的基地台覆蓋範圍
並且遍歷位址陣列
若還能夠覆蓋的話，就不多設一個基地台
反之，就多設一個，修改 $lp$

---

```cpp=
#include <bits/stdc++.h>
#define endl '\n'
#define mid ((l+r)>>1)
using namespace std;
const int maxn = 2e5 + 5 ;
const int mod = 1e9 + 7 ;
const int INF = 1e9 + 9 ;
int p[maxn],n,k;
bool check(int x) {
	int lp=-1,cnt=0;
	for(int i=1;i<=n;i++) {
		if(p[i]>=lp) {
			cnt++;
			lp=p[i]+x/2;
		}
	}
	if(cnt>=k) return false;
	else return true;
}
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>p[i];
	int l=1,r=1e5,ans;
	while(l<=r) {
		if(check(mid)) ans=mid,r=mid;
		else l=mid;
	}
	cout<<ans<<endl;
}
```

---
```
test case:
6 2
5 2 1 7 5 8
_*___*____
00__0_00__
```
---

這個也有在證書題單裡面喔 ~

---

## 來到我們的歡樂的模擬考前
## 複習時間 ~
---

## 第一堂課

---

1. 萬用標頭檔
```cpp=
#include <bits/stdc++.h>
```
2. #define (a) (b)
```cpp=
#define int long long
#define endl '\n'
#define add(a,b) (a+b)
#define pb push_back
```
3. 時間複雜度 O()
```cpp=
// O(n)
for(int i=0;i<n;i++) cout<<i<<'\n';

// O(n^2)
for(int i=0;i<n;i++) 
    for(int j=0;j<n;j++) 
        cout<<j<<'\n';

// O(logn)
    std::lower_bound(arr,arr+n,3)
        
```
4. struct 結構體
```cpp=
struct strc {
    int a,b;
    char ch;
    int add() {
        return a+b;
    }
} strc1,strc2[10];
strc1.add()
int add(strc s1) {
    return s1.a+s1.b;
}
```
5. 自訂函數
```cpp=
int printnum(int x) {
    cout<<x<<endl;
    return x;
}
```
6. 排序 & 自訂排序
```cpp=
bool compare(int a,int b) {
    return a<b;
}
std::sort(arr,arr+n);
std::sort(arr,arr+n,greater<int>());
std::sort(arr,arr+n,compare);
```
7. 常見函式
```cpp=
std::swap(a,b);
std::min(a,b);
std::max(a,b);
```
---

## 第二堂課

1. 簡單遞迴語法
```cpp=
int print(x) {
    if(x<=0) return 0;
    cout<<"First output of"<<x<<':'<<x<<endl;
    int t=print(x-1);
    cout<<"Second output of"<<x<<':'<<t<<endl;
}
```
2. 應用 
```cpp=
//For instance : 
int gcd(int a,int b) {
    if(a==0) return b;
    else return gcd(b,a%b);
}
```



---

## 第三堂課

1. 堆疊 stack 
```cpp=
stack<int>stk;
stk.push(1); // an operation used to push a number on the top of the stack
stk.pop(); // an operation used to pop the number on the top of the stack
stk.size(); // an integer, the size of the stack 
stk.top(); // the top of the stack
stk.empty(); // a boolean number, checking whether the stack is empty or not
```
2. 佇列 queue
```cpp=
queue<int>q;
q.push(1); // an operation used to push a number on the back of the queue
q.pop(); // an operation used to pop a number on the front of the queue
q.size(); // an integer, the size of the queue 
q.front(); // the front of the queue
q.empty(); // a boolean number, checking whether the vector is empty or not
```
3. 動態陣列 (向量?) vector
```cpp=
vector<int>v;
v.push_back(1);
v.pop_back();
v.empty();
v.size();
v.front();
v.back();
v.clear();
v.push_front(); // Please do not use the function because it's time complexity is O(n)
v.pop_front(); // Please do not use the function because it's time complexity is O(n)
v.erase(v.begin()); // Please do not use the function because it's time complexity is O(n)
v.begin();
v.end();
v.resize();
sort(v.begin(),v.end());
.
.
.
// Anyway you can just google it
```
4. 雙向佇列 deque
```cpp=
deque<int>dq;
dq.push_back();
dq.pop_back();
dq.push_front();
dq.pop_front();
dq.size();
dq.empty();
dq[2]; // to be honest, I do not know the exact time complexity of this. Anyway do not use this function.
```
---

[資料結構練習題](https://zerojudge.tw/ShowProblem?problemid=a565)

---

## 第四堂課

---

1. 集合 set
```cpp=
set<int>st; // or multiset<int>st
st.begin(); // *iterator
st.rbegin(); // *reverse_iterator
st.erase(st.find(3));
st.insert(5);
st.clear();
st.empty();
st.size();
```
2. ( 我找不到中文 ) map
```cpp=
O(logn)
map<long long,int>mp;
mp.begin();
mp.rbegin();
mp.erase(4);
mp[5]=6;
mp.clear();
```
3. unordered_map
```cpp=
unordered_map<int,int>mp;
O(1)
```

4. 優先佇列 prioirty_queue
```cpp=
//O(logn)
priority_queue<int>pq;
pq.push(1);
pq.pop();
pq.top();
pq.empty();
pq.size();
```

---

[動態資料結構練習題](http://mdcpp.mingdao.edu.tw/problem/B033)

---

## 第五堂課

---

1. 二分搜 simple_binary search
```cpp=
int simple_binary_search(int* arr[],int n,int k) {
    int l=1,r=n,ans=-1;
    while(l<=r) {
        int mid=(l+r)/2;
        if(arr[mid]>k) {
            r=mid-1;
        } 
        else {
            ans=mid;
            l=mid+1;
        }
    }
    return ans;
}
```
2. 跳躍二分搜 jump_binary_search
```cpp=
int jump_binary_search(int* arr[],int n,int k) {
    for(int i=n;i>0;i=i/2) {
        int pos=0;
        if(arr[pos+i]<=k) {
            ans=pos+i;
            pos+=i;
        }
        else if(arr[pos]<=k) {
            ans=pos;
        }
    }
    return ans;
}
```
3. STL 二分搜
```cpp=
int STL_binary_search(int* arr[],int n,int k) {
    auto it=upper_bound(arr+1,arr+1+n,k);
    return *--it;
}
```
4. 動態二分搜 dynamic binary search
```cpp=
int dynamic_binary_search(set<int>* st,int k) {
    auto it=st.upper_bound(k);
    return *--it;
}
```
5. 外掛二分搜
```cpp=
// 請往上找
```

---

[二分搜練習題](https://zerojudge.tw/ShowProblem?problemid=c179)

---

## 第六堂課

---

1. 外掛二分搜
https://reurl.cc/ARDAke
2. 總複習
https://reurl.cc/35mxa8

