本文主要是介绍二分练习题——妮妮的月饼工厂,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
妮妮的月饼工厂
题目分析
这里出现了“最高高度”,那么可以考虑用二分去做。
第一阶段二段性分析
希望月饼的高度最大,而月饼的高度要满足一个条件,就是按照该高度切出来的月饼的块数应该大于等于K块。那么现在就是满足条件的最大值,我们要看一下他是否符合二段性,二分的关键在于二段性。
对于高度为mid的月饼,如果它可以切出k块月饼,那么我们可以确定高度小于mid的月饼一定也可以,但是此时我需要找的是最大的高度,那么mid一定比小于mid的值更大,所以小于mid的值我就不用管了,也就是我可以确定我能够舍弃掉mid左边的值。我还想要确定比mid更大的高度是否也满足条件,所以我要在mid的右边继续二分。
if (check(mid)) {l = mid;} //因为mid是符合条件的,所以我要留着它,而不是l=mid+1
对于高度为mid的月饼,如果它不可以切出k块月饼,那么我们可以确定边长大于mid的月饼一定也不可以,所以大于等于mid的值我就不用管了,也就是我可以确定我能够舍弃掉mid右边的值。我还想要寻找比mid更小的月饼是否能满足条件,所以我要在mid的左边继续二分。
else { r = mid - 1; }//因为mid是不符合条件的,所以我不要留着它,而不是r=mid
//主要这里出现了减法,那么求mid那么应该是(l+r+1)/2
综上该题满足二段性,可以用二分,二分的板子就不说了,接下来说一下check函数如何写。
第二阶段写check函数
check(u)要实现的作用是检查高度为u的情况下能否切出k块月饼。已知某个月饼高度为 H H H大小,那么能够切出来的月饼个数用 ( H / u ) (H/u) (H/u)表示。那么只需要遍历当前每一块月饼,求出能个切割的月饼总数和k比较就可以了,代码如下,
private static boolean check(int u) {long res = 0l;for(int i = 1;i <=n;i++) {res += a[i]/u;}if(res >= k) return true;return false;
}
第三步二分范围确定
那么这里的高度的最小值是1,最大值就是月饼的最大边长,也就是1e9。注意本题没有说一定能找到符合条件的高度,所以最后输出的时候要判断一下。
题目代码
import java.util.Scanner;
public class Main {static long a[];static int n;static long k;
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();k = scanner.nextLong();a = new long[n+1];for(int i = 1;i<=n;i++) {a[i]=scanner.nextInt();}int l = 1,r = (int) 1e9;while(l < r) {int mid = (l+r+1)/2;if(check(mid)) l = mid;else r = mid-1;}if(!check(l)) System.out.println(-1);//忘了这个判断else System.out.println(l);
}
private static boolean check(int u) {// TODO Auto-generated method stublong res = 0l;for(int i = 1;i <=n;i++) {res += a[i]/u;}if(res >= k) return true;return false;
}
}
这篇关于二分练习题——妮妮的月饼工厂的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!