二分學習筆記

寫在前面

二分是一種常用且非常精妙的算法，常常是我們解決問題的突破口。二分的基本用途是在單調序列或單調函數中做查找。因此當問題的答案具有單調性時，就可以通過二分把求解轉化為判定。進一步地，我們還可以通過三分法解決單調函數的極值以及相關問題。

刷題進度

二分答案（2/4）

二分查找

問題解決進度

Q1

---

?

一、二分

二分法，在一個單調有序的集合或函數中查找一個解，每次分為左右兩部分，判斷在哪個部分中并調整上下界，直到找到目標元素，每次二分后都將舍棄一半的查找空間，因此效率很高。

顯然，二分算法的復雜度為O(二分次數×單次判定復雜度)

……可憐的我依舊不會算復雜度QAQ……

---

二、二分核心代碼

1.整數定義域

int work(int l,int r){int l=-INF,r=INF;//根據題目要求改變左右端點的初始值while(l<r){int mid=(l+r)>>1;if(check(mid+1)) l=mid+1;//如果符合要求就繼續二分查找else r=mid;}return l;
}

2.實數定義域

double work(double l,double r){//根據題目要求確定精度dltdouble mid;while(fabs(l-r)>dlt){//實數比較大小，此句相當于l<r
//補充:fabs(x1)很abs(x2)都表示求絕對值，只不過x1是實數，x2是整數mid=(l+r)/2.0;if(check(mid)) r=mid;else l=mid;}return l;
}

TIP：如果指定二分的次數為t，那么對于初始的求解區間長度L，算法結束后r-l的值為L/2^t

---

?

三、二分法常見模型

1.二分答案

最小值最大（或最大值最小）問題，這類雙最值問題常常選用二分法求解，也就是確定答案后，配合貪心、DP等其他算法檢驗這個答案是否合理，將最優化問題轉換為判定性問題。

【例 1】

將長度為n的序列分成最多m個連續段，求所有分法中每段和的最大值的最小是多少？

一些題目

LuoguP1024

LuoguP2678

LuoguP3957

Luogu二分答案

2.二分查找

用具有單調性的布爾表達式求解分界點。

【例 2】

在有序數列中求數字x的排名。

一些題目

Luogu二分查找

3.代替三分

有時，對于一些單峰函數，我們可以用二分導函數的方法求解函數極值，這時通常將函數的定義域定義為整數域求解比較方便。

---

?

四、典型例題

【例 1】憤怒的牛(Bzoj 1734)

1.題目大意

已知有n間牛舍和每間牛舍的位置，現在要求一種方案使得m頭牛兩兩之間的最小距離盡可能大，求這個最大的最小距離。

2.思路

這是一道最大值最小化的典型題目。

設C(d)表示可以安排牛的位置，并使得最近的兩頭牛距離≥d

那么問題就轉化為了求滿足C(d)的最大的d，最近的間距≥d可以看成是所有間距都≥d，因此滿足C(d)的條件就是任意兩頭牛的位置≥d

于是可以貪心求解：

<1>對牛舍的位置x進行排序

<2>把第一頭牛放入x₀的牛舍

<3>如果第i頭牛放入了x_j的牛舍，則第i+1頭牛就要放入滿足x_j+d≤x_k的x_k最小的牛舍中

對x的排序只要在開始時進行一次就可以了，每一次判斷對每頭牛最多進行一次處理，因此算法的時間復雜度為O(nlogn)

3.代碼

咕咕咕咕咕

【例 2】Best Cow Fences(Poj 2018)

1.題目大意

給定一個長度為n的正整數序列A，求一個平均數最大的，長度≥L的子序列。

2.思路

二分答案mid，合法的條件為“存在一個長度≥L的子序列，平均數≥mid”

如果把數列中的每個數都減去二分的值，合法的條件就轉化為“存在一個長度≥L的子序列，子序列每一項相加的和≥0”

接下來就是著重解決兩個問題：

<1>求一個子序列，要求和最大，沒有“長度≥L”的限制

無長度限制的最大子序列和問題是一個經典問題，只需O(n)掃描該數列，不斷地把新的數加入子序列，當子序列的和變成負數時，把當前的整個子序列清空。掃描過程中出現的最大子序列和即為所求。

<2>求一個子序列，要求和最大，且子序列的長度≥L

子序列和可以轉化為前綴和相減的形式，即設sum_i表示A₁～A_i的和，則有：

max_i-j≥L{A_j+1+A_j+2+……+A_i}=max_L≤i≤n{sum_i-min_0≤j≤i-L{sum_j}}

這個式子啥意思呀？QAQ

這個式子隨著i的增長，j的取值范圍0～i-L每次只會增加1。也就是說，每次只會有一個新的值進入min{sum_j}的候選集合，所以沒有必要每次循環枚舉j次，只需要用一個變量記錄當前最小值，每次與新的取值sum_i-L取min就可以了。

解決了這兩個問題后，我們只需要判斷最大子序列和是不是非負數，就可以確定二分上下界的變化范圍了。

3.代碼

咕咕咕咕咕