class051 二分答案法与相关题目【算法】

package class051;
// 爱吃香蕉的珂珂
// 珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉
// 警卫已经离开了，将在 h 小时后回来。
// 珂珂可以决定她吃香蕉的速度 k （单位：根/小时)
// 每个小时，她将会选择一堆香蕉，从中吃掉 k 根
// 如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉
// 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
// 返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）
// 测试链接 : https://leetcode.cn/problems/koko-eating-bananas/
public class Code01_KokoEatingBananas {
  // 时间复杂度O(n * log(max))，额外空间复杂度O(1)
  public static int minEatingSpeed(int[] piles, int h) {
    // 最小且达标的速度，范围[l,r]
    int l = 1;
    int r = 0;
    for (int pile : piles) {
      r = Math.max(r, pile);
    }
    // [l,r]不停二分
    int ans = 0;
    int m = 0;
    while (l <= r) {
      // m = (l + r) / 2
      m = l + ((r - l) >> 1);
      if (f(piles, m) <= h) {
        // 达标！
        // 记录答案，去左侧二分
        ans = m;
        // l....m....r
        // l..m-1
        r = m - 1;
      } else {
        // 不达标
        l = m + 1;
      }
    }
    return ans;
  }
  // 香蕉重量都在piles
  // 速度就定成speed
  // 返回吃完所有的香蕉，耗费的小时数量
  public static long f(int[] piles, int speed) {
    long ans = 0;
    for (int pile : piles) {
      // (a/b)结果向上取整，如果a和b都是非负数，可以写成(a+b-1)/b
      // "讲解032-位图"讲了这种写法，不会的同学可以去看看
      // 这里不再赘述
      ans += (pile + speed - 1) / speed;
    }
    return ans;
  }
}

package class051;
// 分割数组的最大值(画匠问题)
// 给定一个非负整数数组 nums 和一个整数 m
// 你需要将这个数组分成 m 个非空的连续子数组。
// 设计一个算法使得这 m 个子数组各自和的最大值最小。
// 测试链接 : https://leetcode.cn/problems/split-array-largest-sum/
public class Code02_SplitArrayLargestSum {
  // 时间复杂度O(n * log(sum))，额外空间复杂度O(1)
  public static int splitArray(int[] nums, int k) {
    long sum = 0;
    for (int num : nums) {
      sum += num;
    }
    long ans = 0;
    // [0,sum]二分
    for (long l = 0, r = sum, m, need; l <= r;) {
      // 中点m
      m = l + ((r - l) >> 1);
      // 必须让数组每一部分的累加和 <= m，请问划分成几个部分才够!
      need = f(nums, m);
      if (need <= k) {
        // 达标
        ans = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return (int) ans;
  }
  // 必须让数组arr每一部分的累加和 <= limit，请问划分成几个部分才够!
  // 返回需要的部分数量
  public static int f(int[] arr, long limit) {
    int parts = 1;
    int sum = 0;
    for (int num : arr) {
      if (num > limit) {
        return Integer.MAX_VALUE;
      }
      if (sum + num > limit) {
        parts++;
        sum = num;
      } else {
        sum += num;
      }
    }
    return parts;
  }
}

package class051;
// 机器人跳跃问题
// 机器人正在玩一个古老的基于DOS的游戏
// 游戏中有N+1座建筑，从0到N编号，从左到右排列
// 编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位
// 起初机器人在编号为0的建筑处
// 每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E
// 下一步它将跳到第个k+1建筑
// 它将会得到或者失去正比于与H(k+1)与E之差的能量
// 如果 H(k+1) > E 那么机器人就失去H(k+1)-E的能量值，否则它将得到E-H(k+1)的能量值
// 游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位
// 现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏
// 测试链接 : https://www.nowcoder.com/practice/7037a3d57bbd4336856b8e16a9cafd71
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Code03_RobotPassThroughBuilding {
  public static int MAXN = 100001;
  public static int[] arr = new int[MAXN];
  public static int n;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval;
      int l = 0;
      int r = 0;
      for (int i = 1; i <= n; i++) {
        in.nextToken();
        arr[i] = (int) in.nval;
        r = Math.max(r, arr[i]);
      }
      out.println(compute(l, r, r));
    }
    out.flush();
    out.close();
    br.close();
  }
  // [l,r]通关所需最小能量的范围，不停二分
  // max是所有建筑的最大高度
  // 时间复杂度O(n * log(max))，额外空间复杂度O(1)
  public static int compute(int l, int r, int max) {
    int m, ans = -1;
    while (l <= r) {
      // m中点，此时通关所需规定的初始能量
      m = l + ((r - l) >> 1);
      if (f(m, max)) {
        ans = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return ans;
  }
  // 初始能量为energy，max是建筑的最大高度，返回能不能通关
  // 为什么要给定建筑的最大高度？
  public static boolean f(int energy, int max) {
    // 注意！
    // 如果给的能量值很大，那么后续能量增长将非常恐怖
    // 完全有可能超出long的范围
    // 所以要在遍历时，一定要加入energy >= max的判断
    // 一旦能量超过高度最大值，后面肯定通关了，可以提前返回了
    // 这里很阴
    for (int i = 1; i <= n; i++) {
      if (energy <= arr[i]) {
        energy -= arr[i] - energy;
      } else {
        energy += energy - arr[i];
      }
      if (energy >= max) {
        return true;
      }
      if (energy < 0) {
        return false;
      }
    }
    return true;
  }
}

package class051;
import java.util.Arrays;
// 找出第K小的数对距离
// 数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
// 给你一个整数数组 nums 和一个整数 k
// 数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length
// 返回 所有数对距离中 第 k 小的数对距离。
// 测试链接 : https://leetcode.cn/problems/find-k-th-smallest-pair-distance/
public class Code04_FindKthSmallestPairDistance {
  // 时间复杂度O(n * log(n) + log(max-min) * n)，额外空间复杂度O(1)
  public static int smallestDistancePair(int[] nums, int k) {
    int n = nums.length;
    Arrays.sort(nums);
    int ans = 0;
    // [0, 最大-最小]，不停二分
    for (int l = 0, r = nums[n - 1] - nums[0], m, cnt; l <= r;) {
      // m中点，arr中任意两数的差值 <= m
      m = l + ((r - l) >> 1);
      // 返回数字对的数量
      cnt = f(nums, m);
      if (cnt >= k) {
        ans = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return ans;
  }
  // arr中任意两数的差值 <= limit
  // 这样的数字配对，有几对？
  public static int f(int[] arr, int limit) {
    int ans = 0;
    // O(n)
    for (int l = 0, r = 0; l < arr.length; l++) {
      // l......r r+1
      while (r + 1 < arr.length && arr[r + 1] - arr[l] <= limit) {
        r++;
      }
      // arr[l...r]范围上的数差值的绝对值都不超过limit
      // arr[0...3]
      // 0,1
      // 0,2
      // 0,3
      ans += r - l;
    }
    return ans;
  }
}

package class051;
// 同时运行N台电脑的最长时间
// 你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries
// 其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟
// 你想使用这些电池让 全部 n 台电脑 同时 运行。
// 一开始，你可以给每台电脑连接 至多一个电池
// 然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，你可以进行这个操作 任意次
// 新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池
// 断开连接和连接新的电池不会花费任何时间。
// 注意，你不能给电池充电。
// 请你返回你可以让 n 台电脑同时运行的 最长 分钟数。
// 测试链接 : https://leetcode.cn/problems/maximum-running-time-of-n-computers/
public class Code05_MaximumRunningTimeOfNComputers {
  // 单纯的二分答案法
  // 提交时把函数名改为maxRunTime
  // 时间复杂度O(n * log(sum))，额外空间复杂度O(1)
  public static long maxRunTime1(int num, int[] arr) {
    long sum = 0;
    for (int x : arr) {
      sum += x;
    }
    long ans = 0;
    // [0, sum]，不停二分
    for (long l = 0, r = sum, m; l <= r;) {
      // m中点，让num台电脑共同运行m分钟，能不能做到
      m = l + ((r - l) >> 1);
      if (f1(arr, num, m)) {
        ans = m;
        l = m + 1;
      } else {
        r = m - 1;
      }
    }
    return ans;
  }
  // 让num台电脑共同运行time分钟，能不能做到
  public static boolean f1(int[] arr, int num, long time) {
    // 碎片电量总和
    long sum = 0;
    for (int x : arr) {
      if (x > time) {
        num--;
      } else {
        // x <= time，是碎片电池
        sum += x;
      }
      if (sum >= (long) num * time) {
        // 碎片电量 >= 台数 * 要求
        return true;
      }
    }
    return false;
  }
  // 二分答案法 + 增加分析(贪心)
  // 提交时把函数名改为maxRunTime
  // 时间复杂度O(n * log(max))，额外空间复杂度O(1)
  public static long maxRunTime2(int num, int[] arr) {
    int max = 0;
    long sum = 0;
    for (int x : arr) {
      max = Math.max(max, x);
      sum += x;
    }
    // 就是增加了这里的逻辑
    if (sum > (long) max * num) {
      // 所有电池的最大电量是max
      // 如果此时sum > (long) max * num，
      // 说明 : 最终的供电时间一定在 >= max，而如果最终的供电时间 >= max
      // 说明 : 对于最终的答案X来说，所有电池都是课上讲的"碎片拼接"的概念
      // 那么寻找 ? * num <= sum 的情况中，尽量大的 ? 即可
      // 即sum / num
      return sum / num;
    }
    // 最终的供电时间一定在 < max范围上
    // [0, sum]二分范围，可能定的比较粗，虽然不影响，但毕竟是有点慢
    // [0, max]二分范围！更精细的范围，二分次数会变少
    int ans = 0;
    for (int l = 0, r = max, m; l <= r;) {
      m = l + ((r - l) >> 1);
      if (f2(arr, num, m)) {
        ans = m;
        l = m + 1;
      } else {
        r = m - 1;
      }
    }
    return ans;
  }
  public static boolean f2(int[] arr, int num, int time) {
    // 碎片电量总和
    long sum = 0;
    for (int x : arr) {
      if (x > time) {
        num--;
      } else {
        sum += x;
      }
      if (sum >= (long) num * time) {
        return true;
      }
    }
    return false;
  }
}

package class051;
import java.util.PriorityQueue;
// 计算等位时间
// 给定一个数组arr长度为n，表示n个服务员，每服务一个人的时间
// 给定一个正数m，表示有m个人等位，如果你是刚来的人，请问你需要等多久？
// 假设m远远大于n，比如n <= 10^3, m <= 10^9，该怎么做是最优解？
// 谷歌的面试，这个题连考了2个月
// 找不到测试链接，所以用对数器验证
public class Code06_WaitingTime {
  // 堆模拟
  // 验证方法，不是重点
  // 如果m很大，该方法会超时
  // 时间复杂度O(m * log(n))，额外空间复杂度O(n)
  public static int waitingTime1(int[] arr, int m) {
    // 一个一个对象int[]
    // [醒来时间，服务一个客人要多久]
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
    int n = arr.length;
    for (int i = 0; i < n; i++) {
      heap.add(new int[] { 0, arr[i] });
    }
    for (int i = 0; i < m; i++) {
      int[] cur = heap.poll();
      cur[0] += cur[1];
      heap.add(cur);
    }
    return heap.peek()[0];
  }
  // 二分答案法
  // 最优解
  // 时间复杂度O(n * log(min * w))，额外空间复杂度O(1)
  public static int waitingTime2(int[] arr, int w) {
    int min = Integer.MAX_VALUE;
    for (int x : arr) {
      min = Math.min(min, x);
    }
    int ans = 0;
    for (int l = 0, r = min * w, m; l <= r;) {
      // m中点，表示一定要让服务员工作的时间！
      m = l + ((r - l) >> 1);
      // 能够给几个客人提供服务
      if (f(arr, m) >= w + 1) {
        ans = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return ans;
  }
  // 如果每个服务员工作time，可以接待几位客人（结束的、开始的客人都算）
  public static int f(int[] arr, int time) {
    int ans = 0;
    for (int num : arr) {
      ans += (time / num) + 1;
    }
    return ans;
  }
  // 对数器测试
  public static void main(String[] args) {
    System.out.println("测试开始");
    int N = 50;
    int V = 30;
    int M = 3000;
    int testTime = 20000;
    for (int i = 0; i < testTime; i++) {
      int n = (int) (Math.random() * N) + 1;
      int[] arr = randomArray(n, V);
      int m = (int) (Math.random() * M);
      int ans1 = waitingTime1(arr, m);
      int ans2 = waitingTime2(arr, m);
      if (ans1 != ans2) {
        System.out.println("出错了!");
      }
    }
    System.out.println("测试结束");
  }
  // 对数器测试
  public static int[] randomArray(int n, int v) {
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = (int) (Math.random() * v) + 1;
    }
    return arr;
  }
}

package class051;
// 刀砍毒杀怪兽问题
// 怪兽的初始血量是一个整数hp，给出每一回合刀砍和毒杀的数值cuts和poisons
// 第i回合如果用刀砍，怪兽在这回合会直接损失cuts[i]的血，不再有后续效果
// 第i回合如果用毒杀，怪兽在这回合不会损失血量，但是之后每回合都损失poisons[i]的血量
// 并且你选择的所有毒杀效果，在之后的回合都会叠加
// 两个数组cuts、poisons，长度都是n，代表你一共可以进行n回合
// 每一回合你只能选择刀砍或者毒杀中的一个动作
// 如果你在n个回合内没有直接杀死怪兽，意味着你已经无法有新的行动了
// 但是怪兽如果有中毒效果的话，那么怪兽依然会在血量耗尽的那回合死掉
// 返回至少多少回合，怪兽会死掉
// 数据范围 : 
// 1 <= n <= 10^5
// 1 <= hp <= 10^9
// 1 <= cuts[i]、poisons[i] <= 10^9
// 本题来自真实大厂笔试，找不到测试链接，所以用对数器验证
public class Code07_CutOrPoison {
  // 动态规划方法(只是为了验证)
  // 目前没有讲动态规划，所以不需要理解这个函数
  // 这个函数只是为了验证二分答案的方法是否正确的
  // 纯粹为了写对数器验证才设计的方法，血量比较大的时候会超时
  // 这个方法不做要求，此时并不需要理解，可以在学习完动态规划章节之后来看看这个函数
  public static int fast1(int[] cuts, int[] poisons, int hp) {
    int sum = 0;
    for (int num : poisons) {
      sum += num;
    }
    int[][][] dp = new int[cuts.length][hp + 1][sum + 1];
    return f1(cuts, poisons, 0, hp, 0, dp);
  }
  // 不做要求
  public static int f1(int[] cuts, int[] poisons, int i, int r, int p, int[][][] dp) {
    r -= p;
    if (r <= 0) {
      return i + 1;
    }
    if (i == cuts.length) {
      if (p == 0) {
        return Integer.MAX_VALUE;
      } else {
        return cuts.length + 1 + (r + p - 1) / p;
      }
    }
    if (dp[i][r][p] != 0) {
      return dp[i][r][p];
    }
    int p1 = r <= cuts[i] ? (i + 1) : f1(cuts, poisons, i + 1, r - cuts[i], p, dp);
    int p2 = f1(cuts, poisons, i + 1, r, p + poisons[i], dp);
    int ans = Math.min(p1, p2);
    dp[i][r][p] = ans;
    return ans;
  }
  // 二分答案法
  // 最优解
  // 时间复杂度O(n * log(hp))，额外空间复杂度O(1)
  public static int fast2(int[] cuts, int[] poisons, int hp) {
    int ans = Integer.MAX_VALUE;
    for (int l = 1, r = hp + 1, m; l <= r;) {
      // m中点，一定要让怪兽在m回合内死掉，更多回合无意义
      m = l + ((r - l) >> 1);
      if (f(cuts, poisons, hp, m)) {
        ans = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return ans;
  }
  // cuts、posions，每一回合刀砍、毒杀的效果
  // hp：怪兽血量
  // limit：回合的限制
  public static boolean f(int[] cuts, int[] posions, long hp, int limit) {
    int n = Math.min(cuts.length, limit);
    for (int i = 0, j = 1; i < n; i++, j++) {
      hp -= Math.max((long) cuts[i], (long) (limit - j) * (long) posions[i]);
      if (hp <= 0) {
        return true;
      }
    }
    return false;
  }
  // 对数器测试
  public static void main(String[] args) {
    // 随机测试的数据量不大
    // 因为数据量大了，fast1方法会超时
    // 所以在数据量不大的情况下，验证fast2方法功能正确即可
    // fast2方法在大数据量的情况下一定也能通过
    // 因为时间复杂度就是最优的
    System.out.println("测试开始");
    int N = 30;
    int V = 20;
    int H = 300;
    int testTimes = 10000;
    for (int i = 0; i < testTimes; i++) {
      int n = (int) (Math.random() * N) + 1;
      int[] cuts = randomArray(n, V);
      int[] posions = randomArray(n, V);
      int hp = (int) (Math.random() * H) + 1;
      int ans1 = fast1(cuts, posions, hp);
      int ans2 = fast2(cuts, posions, hp);
      if (ans1 != ans2) {
        System.out.println("出错了!");
      }
    }
    System.out.println("测试结束");
  }
  // 对数器测试
  public static int[] randomArray(int n, int v) {
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) {
      ans[i] = (int) (Math.random() * v) + 1;
    }
    return ans;
  }
}

输入
3 10 20
7 9 6
输出
10

/*
工厂可以生产n种糖果，糖果编号为1到n，工厂每天生产i号糖果的数量为arr【i】，不同编号的糖果并行生产。
工厂接到一个订单，要求是a包糖果、每包糖果必须是同一种类、每包的数量不能少于b个。
一种糖果可以生产很多包。返回至少需要多少天才能完成订单。
解法：根据天数二分。假设生产x天，那么每号糖果都可以算出生产x天能凑几包，然后看看所有糖果能不能凑够a包。
凑不够在x右侧二分；凑够让ans=x，去x左侧二分。学起来吧！二分答案法真的重要！
输入
3 10 20
7 9 6
输出
10
 */
public class Main {
    public static void main(String[] args) {
        int n=3;
        int a=10;
        int b=20;
        int[] arr=new int[]{7,9,6};
        int max=0;
        for (int i = 0; i < n; i++) {
            max=Math.max(max,arr[i]);
        }
        int l=1;
        int r=a*b/max;
        int res=0;
        while (l<=r){
            int m=(l+r)/2;
            int cur=f(arr,b,m);
            if(cur>=a){
                res=m;
                r=m-1;
            }else {
                l=m+1;
            }
        }
        System.out.println(res);
    }
    //生产x天，每包b个，能够有多少包糖果
    public static int f(int[] arr,int b,int x){
        int res=0;
        for (int n:arr){
            res+=n*x/b;
        }
        return res;
    }
}