二分查找与二分答案(3)

例1

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

 上图是一块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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT可乐

深入理解计算机系统(2.7)------浮点数舍入以及运算

  上一篇博客我们讲解了二进制小数如何表示以及IEEE浮点标准。而且我们也提到过因为这种表示方法限制了浮点数的范围和精度,浮点数只能近似的表示一个数。   比如...

2806
来自专栏生信宝典

R语言学习 - 热图美化

热图美化 上一期的绘图命令中,最后一行的操作抹去了之前设定的横轴标记的旋转,最后出来的图比较难看。 上次我们是这么写的 p <- p + xlab("samp...

3148
来自专栏IMWeb前端团队

说一说z-index容易被忽略的那些特性

前言 关于z-index,每个人都会用,但大多人都不理解其真正的生效机制。最近做项目有很多用到z-index的地方,才发现以前用的一知半解,所以上网查了一些资料...

3995
来自专栏十月梦想

js实现随求抓取样本数据(批量或者样本元素)

马上期末汇报学期项目了,这个居然要随机点名汇报,突然想起是否可以使用筛选数据,批量抽取样本中数据进行排序!

792
来自专栏阿凯的Excel

物料管理小能手(统计不重复数据)

平时的仓库物料管理,有很多种材料要进进出出。 如果是用Excel做手工台账的,可以看看我的分享! 我有手工台账如下: ? 小本买卖,上面都是便利店的王牌销售...

2694
来自专栏小樱的经验随笔

2017 Multi-University Training Contest - Team 1 1003&&HDU 6035 Colorful Tree【树形dp】

Colorful Tree Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131...

2534
来自专栏我爱编程

Matplotlib入门

qiangbo.space/2018-04-06/matplotlib_l1/ 入门代码示例 import matplotlib.pyplot as plt ...

3639
来自专栏SeanCheney的专栏

《Pandas Cookbook》第01章 Pandas基础

公司网址,http://www.dunderdata.com(dunder是蒸馏朗姆酒的残留液体,取这个名字是类比数据分析过程) GitHub地址:https...

612
来自专栏专知

【 关关的刷题日记50】 Leetcode 345. Reverse Vowels of a String

关关的刷题日记50 – Leetcode 345. Reverse Vowels of a String 题目 Write a function that ta...

2543
来自专栏PPV课数据科学社区

【学习】请速度收藏,Excel常用电子表格公式大全

1、查找重复内容公式:=IF(COUNTIF(A:A,A2)>1,”重复”,””)。 2、用出生年月来计算年龄公式:=TRUNC((DAYS360(H6,”2...

3448

扫码关注云+社区