二分查找法：在女朋友回家之前可以玩多少个游戏？
题目描述
小猿喜欢玩电子游戏。他在 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^4piles.length <= H <= 10^91 <= 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(10, 9);
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;
}
}
更多相关文章
- C语言的一些练习以及自己写一个猜数字小游戏
- 【春节特辑】24 点游戏
- 【春节特辑】弹珠抽奖游戏概率
- C语言的一些练习以及写一个猜数字游戏
- 手把手教你使用Pygame制作飞机大战小游戏，4万字超详细讲解！
- 童年的游戏，Python一行代码就能玩
- 快速提高Python数据分析速度的八个技巧
- 最快速度安装php（centos8）！