二分

二分

二分是一个经典思想，包含二分查找和二分答案

1 二分查找

在一串升序排列的数字中，找到某一个数字 $k$

思路： 维护一个左右边界 $l,r$，其中初始时, $l=\min (a_n){|}_n,r=\max (a_n){|}_n$ (即最大值和最小值的下标)

进行循环，直到 $l>r$,在每个循环做如下操作

1. 维护一个$mid$, 其为$mid=(l+r+1)/2$
2. 判断$a_{mid}=k$ 是否成立
   1. 如果$a_{mid}<k$ 则让 l = mid + 1；
   2. 如果$a_{mid}>k$ 则让 r = mid - 1;
3. 跳出循环，此时mid即为数$k$的下标

2 二分答案

二分答案是在优化循环时常用的思路，当我们发现一般循环思路难以在规定时间下解决问题的时候可以考虑进行二分答案
思路如下:

1. 假设得到的答案为 $\omega$ ，设立 $l,r$ 作为答案 $\omega$ 的范围
2. 进行循环：每次将 $\omega$ 赋值为 (l + r + 1)/2
3. 通过得到的 $\omega$ 在题意下推理
   1. 如果$\omega$符合题意，说明仍然存在范围，可以继续缩小$\omega$
   2. 如果不符合题意，说明已经超出范围，需要扩大范围
4. 循环结束，此时 $\omega$ 为最优解

最大连号数问题

例：
有$n$个房间，每个房间只能容纳一个人，当两个及以上房间都有人时称为房间连号，连号数等于这一段同时有人的房间的数量，现在有$k$个人要被分配到房间里，请你找出最佳分配方式使得最大连号数最小,我们保证 $k\le n$

思路：

• 使用二分答案查找一个数 $m$ ，对于每个猜测的$m$，我们需要验证是否存在一种分配方式，使得所有连号数不超过$m$，并且恰好分配$k$个人
• 验证思路：
  • 对于每个候选的$m$，计算在最大连号数不超过$m$的情况下，最多可以安排多少人。这通过将房间分成多个段，每个段最多$m$人，段之间至少有一个空房间来实现。如果这种安排下的人数大于等于$k$，则$m$是可行的
  • 具体思路：
    • 确定 $mid=(l+r)/2$ ,这里的mid我们将其当作可以放下的最大连号数
    • 进入循环：
      1. $c1=n/(mid+1)$ 表示在这个最大连号数下房间可以被分成几块
         • 因为两个连号房间之间得隔着一个空房间，所以是mid + 1
      2. $c2=n-c1\ast (mid+1)$ 表示在n个房间中分完了后剩下的部分
      3. 计算在 $mid$ 条件下能放下的人数ans
      4. 比较 ans 与题目人数 k
    • 若 $ans\ge k$ 说明可以放下的人数超过题目人数，可以缩减人数范围
    • 若 $ans<k$ 则说明要扩大人数范围

void solve() {
    int n, k;
    cin >> n >> k;
    int l = 0, r = k,ans = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        auto check = [&]() -> bool {
            int ans1 = 0;
            int c1 = n / (mid + 1);
            int c2 = n - c1 * (mid+1);
            ans1 += c1 * mid + c2;
            return ans1 >= k;
        };
        if(check()){
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
        
    }
    cout << ans;
}