# 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
Sign in with Wallet
Connect another wallet