二分查找与二分答案（3）

例 1展开目录

关于从长方形的巧克力中切出正方形的小巧克力，可以看下面的示意图：

上图是一块 5x6 的巧克力分别切出 1x1、2x2 和 3x3 的示意图。切成 1x1 一共可以切出 30 块，切成 2x2 可以切出 6 块。四个 1 是一块，四个 2 是一块，以此类推。切成 3x3 一共可以切出 2 块。用公式来说的话，一块 HxW 的巧克力，如果要切出边长是 x 的正方形，一共可以切出 $\lfloor \frac {H}{x} \rfloor \times \lfloor \frac {W}{x} \rfloor$ 块正方形的巧克力

现在题目的要求是，在保证至少切出 K 块正方形巧克力的前提下，要正方形的边长越大越好。首先我们应该很容易想到，正方形的边长越大，能切出来的数量就越少

比如我们看样例是一块 5x6 的巧克力和一块 6x5 的巧克力。如果边长是 1，那么一共可以切出来 30+30=60 块；如果边长是 2，那么一共可以切出来 6+6=12 块；如果边长是 3，那么一共可以切出来 2+2=4 块；如果边长是 4，那么一共可以切出来 1+1=2 块。如果边长是 5，那么也是 2 块。

因为题目要求至少保证 10 块，所以答案就是 2。因为边长是 2 可以切出 12 块；而再大一点边长是 3 的话就只能切出 6 块了。

思路 1 暴力枚举展开目录

从小到大枚举边长 x；对于确定的 x，计算 N 块巧克力一共能切出多少边长为 x 的正方形；如果数量大于等于 K，记录当前的 x 作为答案；否则说明边长 x 已经过大，直接退出枚举。伪代码如下：

For X = 1...100000
Cnt = 0
For i = 1...N
    Cnt += (H[i]/x)*(w[i]/x)
    If(cnt >= x)
        Ans = x
    else
        break
print Ans

上面枚举边长 x 的复杂度是 $O (Ans)$，然后枚举所有的巧克力，计算能切出的正方形数量，复杂度是 $O (N)$，所以整个程序的时间复杂度是 $O (Ans*N)$，根据题目给的数据范围，很有可能会超时

优化展开目录

假设有一个数组 a [1], a [2], a [3], … a [100000]。其中 a [i] 的值是当 x=i 的时候，总共能切出来的正方形数目。我们现在并不知道每一个 a [i] 的值是多少，但是我们知道可以用一个函数 f (i) 求出来，并且 f (i) 的时间复杂度是 $O (N)$。其次，我们还知道一个重要信息，a 数组是递减的，a [i] 一定大于等于 a [i+1]

而我们的目标是找到最大的边长 x，实际上就是找到 a 数组中，值大于等于 K，并且下标最大的这个下标。我们可以发现这个描述和我们之前的求 lower_bound 很类似。实际上如果我们想象一下把 a 数组首尾颠倒一下，其实就是在颠倒的 a 数组里求 lower_bound (K)。虽然我们现在面对的 a 数组是递减的，不是递增的，但是一样可以用二分查找求解。代码如下：

#include <iostream>
using namespace std;
int n,k,h[100010],w[100010];
bool ok(int m)
{
    long long c = 0;
    for(int i = 0;i < n;i++)
        c += (long long)(h[i] / m) * (w[i] / m);
    if(c >= k)
        return true;
    return false;
}
int main()
{
    cin >> n >> k;
    for(int i = 0;i < n;i++)
        cin >> h[i] >> w[i];
    int ans = 1;
    int l = 1,r = 100000;
    while(l <= r)
    {
        int m = l + (r - l) / 2;
        if(ok(m))
        {
            ans = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    cout << ans;
    return 0;
}

第 9~11 行是在判断假如切出来的正方形边长为 m，数量够不够 k，如果够就返回 ture，否则返回 false

如果 ok (m) 的返回值是 true，说明当前边长 m 满足条件，就先记下来作为答案 ans；边长是 m 满足条件，那么边长是 l~m-1 一定也都满足条件，所以我们只需要再尝试 m+1, m+2, .. r。于是第 24 行我们令 l=m+1

例 2 题目链接：hihoCoder1357展开目录

小 Ho 的城市有 K 层护盾，每层护盾能抵挡 M 点伤害。受了伤但是还没被打爆的护盾可以 “回血”，每秒回一点。同时小 Hi 有 N 枚炮弹，第 i 枚会造成 Ai 点伤害。小 Hi 会按顺序用 N 枚炮弹去攻击小 Ho 的城市，攻击的间隔是 T 秒。所以小 Ho 的护盾如果没被上一发打爆的话，就可以在这 T 秒内回血。

显然攻击间隔越小，小 Ho 撑过 N 次攻击的可能性越小。问要满足小 Ho 的 K 层护盾没有被全部打爆，攻击间隔最小可能是多少

先我们分析一下题目就可以知道。假如攻击间隔 T 是确定的，那么整个攻击 / 回血的过程就确定了，换句话说小 Ho 的 K 层护盾会不会被打爆就是确定的。所以我们可以先实现一个 bool crash(int t) 函数，表示当攻击间隔是 t 秒时，小 Ho 会不会被打爆。伪代码如下：

Bool crash(t)
    C = m,Cnt = 0//C是当前护盾HP，Cnt是击穿了基层护盾
    For i = 1...N
        If A[i] >= C//第i枚炮弹击穿当前护盾
            Cnt++
            C = m
        Else
            C = min(m,C-A[i]+t)
return Cnt >= k//如果击穿k层护盾就返回true

此外，题目描述中也暗示了，攻击间隔越小，护盾越容易被打爆。所以如果我们假设有一个数组，a [1]=crash (1)， a [2]=crash (2), a [3]=crash (3) … 显然这个数组不会 FALSE 排在 TRUE 前面。换言之，从某种意义上讲也是有序的。而我们现在要在 a 数组里找值是 FALSE 的元素中下标最小的元素的下标。显然是可以二分查找的。代码如下：

#include <iostream>
using namespace std;
int n,k,m,a[100000];
bool crash(int t)
{
    int c = m,cnt = 0;
    for(int i = 0;i < n;i++)
    {
        if(a[i] >= c)
        {
            cnt++;
            c = m;
        }
        else
        {
            c = c - a[i] + t;
            if(c > m)
                c = m;
        }
    }
    return cnt >= k;
}
int main()
{
    cin >> n >> m >> k;
    int count = 0;
    for(int i = 0;i < n;i++)
    {
        cin >> a[i];
        if(a[i] >= m)
            count++;
    }
    if(count >= k)
    {
        cout << -1 << endl;
        return 0;
    }
    int l = 1,r = m;
    int ans = m;
    while(l <= r)
    {
        int t = l + (r - l) / 2;
        if(crash(t))
            l = t + 1;
        else
        {
            ans = t;
            r = t - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

注意第 33~37 行，这是在特判一种情况。假如无论攻击间隔多大，小 Ho 的护盾都必定被打爆，那么就输出 - 1。如果不是这种情况，那么 crash (M) 的值一定是 FALSE。因为攻击间隔 M 秒会使得只要没有一发击穿护盾，残血护盾就一定能回满

所以攻击间隔枚举的范围就是 1-M，并且先把 ans 的初始值设为 M。第 40~50 行就是在二分查找，t 是范围 [l, r] 的中点。如果 crash (t) 的值是 TRUE，说明间隔 t 秒被打爆了，所以要继续尝试比 t 更大的攻击间隔；否则说明间隔 t 秒能抗住，那就先把 t 记作答案，然后再尝试比 t 更小的攻击间隔