# SCIST S4 演算法課程_單調性
:::info
時間：04/28 9:00 ~ 18:00
主題：單調性
直播連結：https://www.youtube.com/watch?v=ZSpqd-9H0g0
:::
## 課程內容
- 單調性
- 講義連結：https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FrJpY0i7PS
# 題解
[TOC]
# 二分搜
### [UVa 10530](http://domen111.github.io/UVa-Easy-Viewer/?10530)
---
### [TOJ 55](https://toj.tfcis.org/oj/pro/55/)
撰寫者：fishhh
待補
:::spoiler Code
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n,ary[1000001],t,q,tot=0;
cin>>n;
for(int i=0;i<n;i++)cin>>ary[i];
sort(ary,ary+n);
cin>>t;
for(int x=0;x<t;x++){
tot=0;
cin>>q;
for(int s=0,e=n-1;e>=s;){
int mid=(s+e)/2;
if(q>ary[mid]){
s=mid+1;
}
else if(q<ary[mid]){
e=mid-1;
}
else{
for(int i=mid;i<n;i++){
if(ary[i]==q){
tot++;
}
else{
break;
}
}
for(int i=mid-1;i>=0;i--){
if(ary[i]==q){
tot++;
}
else{
break;
}
}
break;
}
}
cout<<tot<<"\n";
}
}
```
:::
---
### [ZJ h083](https://zerojudge.tw/ShowProblem?problemid=h083)
---
### [ZJ i401](https://zerojudge.tw/ShowProblem?problemid=i401)
---
### [UVa 10567](http://domen111.github.io/UVa-Easy-Viewer/?10567)
---
### [AtCoder typical90_g](https://hackmd.io/@sa072686/AtCoder_typical90_g)
---
### [TOJ 47](https://toj.tfcis.org/oj/pro/47/)
---
### [Kattis massivecardgame](https://open.kattis.com/problems/massivecardgame)
---
### [Kattis bootstrappingnumber](https://open.kattis.com/problems/bootstrappingnumber)
撰寫者：Jun-an
輸入一個整數 $n$，
找出一個數字 $x$，滿足 $x^x$ = $n$。
這裡利用二分搜在 $1$ ~ $n$ 之間找出 $x$，
浮點數的誤差值在 $1e$-$6$ 以內。
輸出的時候建議使用 `fix << precision(7) << x`
:::spoiler 參考程式碼
```cpp=
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
void Bsearch(double n) {
double l = 0, r = n;
for (int i = 0; i < 101; ++i) {
double mid = l + (r - l) / 2;
if (pow(mid, mid) < n) {
l = mid;
}
else {
r = mid;
}
}
cout << fixed << setprecision(10) << l + (r - l) / 2 << '\n';
}
int main() {
double n;
cin >> n;
Bsearch(n);
}
```
:::
---
### [CSES 1620](https://cses.fi/problemset/task/1620/)
撰寫者：fishhh
假設答案是 $ans_t$，如果給機器超過 $ans_t$ 的時間，就一定可以做完。
反之，如果給所有機器小於 $ans_t$ 的時間，就一定做不完。
所以這就是一個單調性！
我們就對於"時間"去二分搜，每次測試可以單獨寫一個函數來判斷這樣的時間下能做出幾個、能不能做超過 $t$ 個，如果可以就縮右界，如果不可以就縮左界。
```cpp=
#include "iostream"
#include "vector"
#include "cmath"
using namespace std;
#define int unsigned long long
vector<int> v;
int test(int t){
int ret=0;
for(int i:v){
ret+=t/i;
}
return ret;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,t,k;
cin>>n>>t;
for(int i=0;i<n;i++){
cin>>k;
v.push_back(k);
}
int now=0,add=31;
add=(1<<add);
while(add){
while(test(now+add)<t){
now+=add;
}
add/=2;
}
cout<<now+1;
}
```
---
### [ZJ c575](https://zerojudge.tw/ShowProblem?problemid=c575)
撰寫者：Koying
可以發現到，每個基地台的範圍越大，就越有機會成功。
將範圍當作 $x$，成功與否當作 $y$ 畫成圖可發現此函數具有單調性。
因此我們可以對基地台範圍二分搜，找到一個最小且可成功的範圍。
至於如何檢查合法與否？一個半徑為 $r$ 的基地台，其實就是從起點開始延伸 $2r$，所以我們可以利用一個變數紀錄目前這個基地台的範圍，如果服務點超出了範圍，再新架一個新的基地台，並延伸 $2r$
:::spoiler Code
```cpp=
#define MAXN 100005
#define MAXM 1000005
int n, m;
int x[MAXN];
void sol() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> x[i];
}
sort(x, x + n);
int l = 0, r = x[n - 1], mid = (l + r) / 2;
while (l < r) {
mid = (l + r) / 2;
int now = 0, cnt = 0;
for (int i = 0; i < n; i++) {
if (x[i] > now) {
now = x[i] + mid;
cnt++;
}
}
if (cnt > m) {
l = mid + 1;
}
else
r = mid;
}
cout << r << endl;
}
```
:::
---
### [ZJ h084](https://zerojudge.tw/ShowProblem?problemid=h084)
撰寫者：fishhh
先發現一件事，在 $x$ 由小到大，那麼可以放完這件事成功與否就會類似下面這樣。
x = 1 2 3 4 5
ok= 1 1 1 0 0...
也就是說會有一段 1 再來全部都是 0 所以我們就是要找那個最大的 1 出現的位置。
至於貪心的部分就去看講義有詳細的說明。
:::spoiler
```cpp=
#include "iostream"
using namespace std;
int ary[200010]={},flag[6010]={};
int n,k;
bool test(int x){
int cont = 0,i,j;
for(i=1,j=1;i<=n&&j<=k;i++){
if(ary[i]>=x)cont++;
else{
cont = 0;
}
if(cont==flag[j]){
cont = 0;
j++;
}
}
if(j==k+1){
return 1;
}
return 0;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>ary[i];
for(int i=1;i<=k;i++)cin>>flag[i];
int now = 0;
int add = (1<<28);
while(add){
if(!test(now+add)){
add/=2;
}
else{
now+=add;
}
}
cout<<now<<"\n";
}
```
:::
---
# 單調性
### [CSES 1640](https://cses.fi/problemset/task/1640/)
撰寫者：Eason
用雙指針去找
複雜度：$O(n)$
:::spoiler code
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define ll long long
using namespace std;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
ll n, x;
cin >> n >> x;
vector <pair<ll, ll> > v;
for (int i = 1; i <= n; i++){
ll temp;
cin >> temp;
v.push_back(make_pair(temp, i));
}
sort (v.begin(), v.end());
int l = 0, r = n - 1;
while (true){
ll sum = v[l].first + v[r].first;
if (l == r){
cout << "IMPOSSIBLE\n";
break;
}
else if (sum == x){
cout << v[l].second << ' ' << v[r].second << '\n';
break;
}
else if (sum < x) l++;
else if (sum > x) r--;
}
return 0;
}
```
:::
---
### [AtCoder abc212_c](https://atcoder.jp/contests/abc212/tasks/abc212_c)
撰寫者：fishhh
- $O(n^2)$：
兩兩計算絕對值，求最小。
- $O(n\log n)+O(n \log n)$
先將數列A排序（其實換成數列B也行）。
可以想到一件事情，如果要求"與 $b_i$ 絕對值最小"會有兩種狀況
1. 數列 A 裡面小於 $b_i$ 的最大值
2. 數列 A 裡面大於 $b_i$ 的最小值
分別透過一次二分搜就可以完成了
- $O(n\log n) + O(n)$
將數列 A、B 由小到大排序。
邏輯推論一下，可以知道一件事情：與 $b_i$ 絕對值差最小的兩個在 $a_i$ 裡面的數字，必定相鄰。
例如：
$A = \{1,3,5,10\}$
$B_i = 7$ 與 $B_i$ 絕對值差最小的就是 $5,10$ 它們相鄰。
再推論一下：
因為 $B$ 排序過，故 $b_i \leq b_{i+1}$
所以，如果我們知道與 $b_i$ 絕對值差最小的位置。那麼 $b_{i+1}$ 與數列 $A$ 內絕對值差最小的位置一定大於等於與 $b_i$ 絕對值差最小的位置。
所以只要線性掃過就可以了！！！
:::spoiler 參考程式碼
```cpp=
int ary[200010],bry[200010],bbry[200010];
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>ary[i];
for(int i=1;i<=m;i++)cin>>bry[i];
sort(ary+1,ary+n+1);
sort(bry+1,bry+m+1);
int nm = 1;
bbry[1] = bry[1];
for(int i=2;i<=m;i++){ //去重(bry)
if(bry[i]!=bry[nm]){
bry[++nm] = bry[i];
}
}
m = nm;
int ans = 1e9;
int pt = 1;
for(int i=1;i<=n;i++){
while(pt<m&&bry[pt+1]<=ary[i]){ //如果有等於 那其實不管選左邊還是右邊最後答案都是 0
pt++;
}
ans = min(ans,abs(ary[i]-bry[pt]));
if(pt!=m) ans = min(ans,abs(ary[i]-bry[pt+1]));
}
cout<<ans<<"\n";
}
```
:::
---
### [Kattis downtime](https://open.kattis.com/problems/downtime)
撰寫者：Eason
---
### [CSES 1660](https://cses.fi/problemset/task/1660/)
撰寫者：Eason
題目要求區間 $[l, r]$ 的和要等於 $x$
枚舉左界，在左界固定的情況二分搜右界
若要用前綴和求區間 $[l, r]$ 的和
=> $prefix[r] - prefix[l - 1]$
:::spoiler code
```cpp=
#include<bits/stdc++.h>
#define ll long long
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;
ll arr[200005], prefix[200005];
int n, x;
int bin_search(int lp){
// 左界為 lp
// 在利用二分搜求出右界
int l = lp, r = n + 1;
// 這邊的 l, r 並不是左、右界
// 而是用來二分搜右界的變數
while (l + 1 <= r){
int mid = (l + r) / 2;
ll sum = prefix[mid] - prefix[lp];
if (sum == x){
return 1;
}
else if (sum > x){
r = mid;
}
else{
l = mid + 1;
}
}
return 0;
}
int main(){
weakson;
cin >> n >> x;
prefix[0] = 0;
for (int i = 0; i < n; i++){
cin >> arr[i];
prefix[i + 1] = prefix[i] + arr[i];
}
int ans = 0;
for (int i = 0; i < n; i++){ // 枚舉左界
ans += bin_search (i);
}
cout << ans << '\n';
return 0;
}
```
:::
---
### [AtCoder abc038_c](https://atcoder.jp/contests/abc038/tasks/abc038_c)
撰寫者：fishhh
只需要算有幾個連續的最長單調區間就好。例如數列為 $\{1,2,5,3,5,3,2,3\}$
就可以分成是：$\{1,2,5\} , \{3,5\} , \{3\},\{2,3\}$ 這四組連續的單調嚴格遞增區間。
實作的部分：假設 $ary_i \sim ary_j$ 有單調性，如果 $ary_{j+1}>ary_j$ 那麼這個單調區間就可以包含 $ary_{j+1}$。否則就是創造了一個新的單調區間出來。
:::spoiler
```cpp=
int ary[100010];
void solve(){
int n;
long long ans = 0,acc = 0;
cin>>n;
for(int i=1;i<=n;i++)cin>>ary[i];
for(int i=1;i<=n;i++){
acc++;
if(i==n||ary[i+1]<=ary[i]){
ans += acc*(acc+1)/2;
acc = 0;
}
}
cout<<ans<<"\n";
}
```
:::
---
### [AtCoder abc210_c](https://atcoder.jp/contests/abc210/tasks/abc210_c)
---
### [ZJ g277](https://zerojudge.tw/ShowProblem?problemid=g277)
撰寫者：$Jun$-$an$
這題要在 $[$ $L$ $,$ $R$ $]$ 區間之中找到最小值的位置 $m$
接著將區間分為 $[$ $L$ $,$ $m$ $-$ $1$ $]$ 跟 $[$ $m$ $+$ $1$ $,$ $R$ $]$ 並分別計算出區間總和
區間總和最大的那個即為幸運數字所在的區間
繼續上述步驟直到 $L$ $==$ $R$。
這裡使用前綴和處理區間總合的問題，總和可能會超過 $int$ 範圍，所以要使用 $long$ $long$ 儲存
區間之中的最小值位置 $m$ 則是使用 $pair$ 將數字跟索引值綁在一起由大到小排序，每次查詢時判斷索引值是否在 $L$ ~ $R$ 之間，如果不是就刪掉，重複直到找到符合的。
需要使用 $I/O$ 優化
:::spoiler 程式碼
```cpp=
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define weak ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
int nums[300005] = {0};
long long prefix_sum[300005] = {0};
vector<pair<int, int>> save;
bool cmp(pair<int, int> l, pair<int, int> r) {
return l.first > r.first;
}
int find_min(int L, int R) {
while (true) {
pair<int, int> tmp = save.back();
if (L - 1 <= tmp.second && tmp.second <= R - 1) {
save.pop_back();
return tmp.second;
}
else {
save.pop_back();
}
}
}
int main() {
weak
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> nums[i];
save.push_back(make_pair(nums[i], i));
}
sort(save.begin(), save.end(), cmp);
for (int i = 1; i <= n; ++i) {
prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1];
}
int L = 1, R = n;
while (L < R) {
int mn_idx = find_min(L, R) + 1;
if (prefix_sum[mn_idx - 1] - prefix_sum[L - 1] < prefix_sum[R] - prefix_sum[mn_idx]) {
L = mn_idx + 1;
}
else {
R = mn_idx - 1;
}
}
cout << nums[R - 1] << '\n';
return 0;
}
```
:::
---
### [AtCoder abc224_e](https://atcoder.jp/contests/abc224/tasks/abc224_e)
---
### [CSES 1645](https://cses.fi/problemset/task/1645/)
---
### [TIOJ 1370](https://tioj.ck.tp.edu.tw/problems/1370)
---
### [ZJ f174](https://zerojudge.tw/ShowProblem?problemid=f174)
---
### [CSES 1619](https://cses.fi/problemset/task/1619/)
---
### [AtCoder typical90_bl](https://atcoder.jp/contests/typical90/tasks/typical90_bl)
---
### [ZJ g597](https://zerojudge.tw/ShowProblem?problemid=g597)
---
### [AtCoder abc216_e](https://atcoder.jp/contests/abc216/tasks/abc216_e)
---
### [AtCoder typical90_ab](https://hackmd.io/@sa072686/AtCoder_typical90_ab)
Sign in with Wallet
Connect another wallet