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

例1

image

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

image

 上图是一块5x6的巧克力分别切出1x1、2x2和3x3的示意图。切成1x1一共可以切出30块，切成2x2可以切出6块。四个1是一块，四个2是一块，以此类推。切成3x3一共可以切出2块。用公式来说的话，一块HxW的巧克力，如果要切出边长是x的正方形，一共可以切出⌊H/x]*[W/x]块正方形的巧克力  现在题目的要求是，在保证至少切出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

image

 小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更小的攻击间隔。