二分查找法:在女朋友回家之前可以玩多少个游戏?

点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

二分查找法:在女朋友回家之前可以玩多少个游戏?

作者 | 程序员小吴

来源 | 五分钟学算法

今天分享的题目改编自 LeetCode 第 875 号问题:爱吃香蕉的珂珂。

题目描述

小猿喜欢玩电子游戏。他在 steam 上买了 N 类游戏,各种类型的游戏都有,第 i 类的有  piles[i] 个游戏。

某天,他的女朋友小媛出差,将在 H 天后回来。

小猿可以决定他玩游戏的速度 K (单位:个/天)。每天,他将会选择一类游戏,从中玩 K 个,每个游戏只会玩一遍。如果这类游戏少于 K 个,他将玩过这类的所有游戏,然后进入贤者时间,这一天内不会再玩更多的游戏。

小猿喜欢慢慢的玩游戏,但仍然希望能在女朋友回来之前玩所有的游戏。

现在,需要你求解他可以在 H 天内玩所有游戏的最小速度  K(K 为整数)。

示例 1:

输入: piles = [3,6,7,11], H = 8
输出: 4
解释: 
当 K = 4 时,玩这类游戏所需的时间为[1,2,2,3] ,1 + 2 + 2 + 3 = 8 加起来正好为 8,
而当 K = 3 时,玩这类游戏所需的时间为 [1,2,3,4] ,加起来为 10 > 8,因此最小的 K 为 4。 

示例 2:

输入: piles = [30,11,23,4,20], H = 5
输出: 30

说明

  • 1 <= piles.length <= 10^4
  • piles.length <= H <= 10^9
  • 1 <= piles[i] <= 10^9

题目描述

首先,来思考一下 K 的取值范围。

当出差天数 H 为无穷大时( 分手?),小猿恢复了单身狗的身份,有充足的时间去玩,那么即使每天只玩 1 个游戏,也是能玩遍的,所以 K 的最小值是 1

当出差天数 H 最小等于游戏类型数 N 时,那么每天必须玩任意一类游戏,此时 K 值就应该是某类游戏里面数目最多的个数。根据题目的说明,某类游戏个数最大为 10^9。

所以,K 的范围为 [ 1 , 10^9 ]

那么,问题就变成了在  [ 1 , 10^9 ]  这个区间里去查找 K 的值。

对于有序数组的查找问题,第一想法都是 二分查找法

当然,这道题目属于  二分查找法 的变种问题:找到最小的满足条件的 K ,即二分查找 K 的 lower bound 。

首先假设所有类型的游戏里某一类中含有最多游戏的数目为 M 。

取 1 和 M 的平均数,(1 + M) / 2,按照这个速度看小猿同学能否在 H 天内玩遍所有游戏。

如果不能在 H 天内通关所有游戏,意味着需要尝试更快的速度:K 应该在(1 + M) / 2到 M 之间,再取这个区间的平均数

如果可以在 H 天内通关所有游戏,此时就需要判断 K 是否是最慢的那个速度。

如何判断呢?

降速!判断小猿能否以 (1 + M) / 2 - 1 这个速度通关所有游戏。如果小猿不能以 (1 + M) / 2 - 1 这个速度通关,那么很显然 (1 + M) / 2 就是需要求解的那个最小值。

如果降速都还能玩遍所有游戏,那么就需要在尝试使用更慢的速度:在 1 和 (1 + M) / 2 这个范围去查找那个值。

代码实现

class Solution {
   public int minEatingSpeed(int[] piles, int H) {
        int low = 1;
        int high = pow(109);
        int mid;
        while (low < high) {
            mid = (low + high) / 2;
            if (!canPlayGame(piles, mid, H)) {
                low = mid + 1;
            }
            else {
                high = mid; 
            }
        }
        return low;

    }
    private boolean canPlayGame(int[] piles, int k, int H) {
        int t = 0;
        for (int i: piles) {
            if (i % k != 0) {
                t++;
            }
            t += i / k;
        }
        return t <= H;
    }
}

二分查找法:在女朋友回家之前可以玩多少个游戏?

有热门推荐👇

1.程序员我们就必须承认:这个世界上,有很多问题,就是无解的

2.【GitHub我在 GitHub 上看到了一个丧心病狂的开源项目!

3.【算法动画:七分钟理解什么是KMP算法

4.【数据结构十大经典排序算法动画与解析,看我就够了!

二分查找法:在女朋友回家之前可以玩多少个游戏?

▼ 点击『阅读原文』解锁更多图解 LeetCode 题目

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 二分查找法:在女朋友回家之前可以玩多少个游戏?

我还会在以下平台发布内容

GitHub 哔哩哔哩