前言一、题目描述二、解题思路三、示例代码总结
前言
本题主要考查 二分查找 算法。
提示：以下是本篇文章正文内容，编程语言为Java
一、题目描述 有 K 名字节君，每天下午都要推着推车给字节的同学送下午茶，字节的同学分布在不同的工区，字节的工区分布和字节君的位置分布如下。
在上图中，每个方框内的单位长度为 1。已知字节君的推车可以装无限份下午茶，所以不需要字节君回到初始地点补充下午茶。每个字节君只有两个动作。
把推车向前移动一个单位。
把一份下午茶投放到当前工区。
现在告诉你字节君的数量以及每个工具需要的下午茶个数。请问，所有的字节君最少花费多长时间才能送完所有的下午茶？
示例 1：
输入：
3 3
7 1 1
输出：5
解释：
字节君1：右移->放置->放置->放置->放置
字节君2：右移->放置->放置->放置
字节君3：右移->右移->放置->右移->放置
链接：发下午茶
二、解题思路 本题我们可以很容易得出字节君花费的时间范围：最少可以假设为0；如果只有一个人进行配送花费时间最多，为 工位数+下午茶个数 。因此我们就可以 二分时间 来得到字节君最少花费的时间。
1） 当字节君可以完成配送时，那么说明时间可能多了，因此更新右边界 right = mid；
2） 当字节君不能完成配送时，那么说明时间不够，因此更新左边界 left = mid +1。
下面为判断当前时间 mid 下配送是否完成的思路：
K个字节君依次配送，每人有 res=mid 的时间。对于每个字节君 i，我们判断 res 是否足够配送给当前工位 T[j] 。
1）若足够，则配送，更新时间为 res=res-T[i]-1 ，更新工位 j=j+1.
2）若不够，只能配送部分，等价于将剩余时间分给下一位字节君，其时间为 res = mid+res-j-1 ，mid 为初始时间，res-1 为上个字节君分给的时间，j 为移动到当前工位需要的时间。
3）当下午茶配送完，字节君时间还有剩余，则返回 true，否则返回 false。
import java.util.*;
public class Solution{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int k=sc.nextInt();
int n=sc.nextInt();
int [] T=new int[n];
int sum=n;
for(int i=0;i>1;
if(check(mid,k,T,sum-n)){
right=mid;
}
else{
left=mid+1;
}
}
System.out.println(left);
}
//判断时间为 mid 时是否可以完成配送
public static boolean check(int mid,int k,int T[],int sum){
//每个字节君初始的时间
int res=mid;
//字节君依次配送
for(int i=0,j=0;i=0){
//所有工位已完成配送，时间还有剩余
if(j==T.length){
return true;
}
//当前字节君可以完成当前工位的配送
if(res>T[j]){
//移动的时间
res--;
//放茶的时间
res-=T[j];
//配送下一个工位
j++;
}
//当前字节君不能完成当前工位的配送
else{
//剩余时间分给下一位字节君
res=mid+res-j-1;
break;
}
}
}
return false;
}
总结
本题可以很容易得到答案的一个范围，因此我们就可以通过二分查找来确定最后的答案。
