倒计时48天！
二分
二分模板
判断是否可以二分
（1）单调性
备选答案集是有序的
（2）二段性
在检查了mid是否符合要求之和，我可以舍弃mid左右某一边的答案
两个模板
关键词：满足条件的最小值，最大值最小，某个有序区间内某个数>=或者>key的第一个元素，或者当正确答案在左边时 while(l < r) {
//check函数求当前值为mid情况下是否合法，如果合法，会想更小一点的值是不是合法的，所以会舍弃掉右边，去左边寻找更小的值，即r向左移动，因为mid是合法的，不能不要它，所以r=mid
if(check(mid)) {//满足要求，要求最小，再向左找看有没有更小的也满足要求
r = mid;//因为mid也满足要求，所以要保留
//如果不合法，只能扩大当前值，所以会舍弃掉左边，去右边寻找更大的值，即l向右移动，因为mid是不合法的，直接不要它，所以l=mid+1
}else{
l = mid + 1;//mid不满足要求，直接跳过就行
}
}
假设出现如下情况，l=l,r=l+1,此时mid=l。如果mid = (l+r)/2 （1）check(mid)返回为真，r = mid = l，正常退出 （2）check(mid)返回为假，l = r，正常退出 某个有序区间内某个数<=或者 while(l < r) { long mid = (l+r+1)/2;//注意这里要+1 if(check(mid)) {//满足要求，要求最大，再向右找看有没有更大的也满足要求 l = mid;//因为mid也满足要求，所以要保留 }else{ r = mid - 1;//mid不满足要求，直接跳过就行 } } 对于mid=(l+r)/2，假设出现如下情况，l=l,r=l+1,此时mid=l。如果mid = (l+r)/2 （1）check(mid)返回为真，l = mid = l，此时会陷入无限循环 （2）check(mid)返回为假，r < l，正常退出 对于mid=(l+r+1)/2，假设出现如下情况，l=l,r=l+1,此时mid=l+1。如果mid = (l+r+1)/2 （1）check(mid)返回为真，l = mid = l+1=r，正常退出 （2）check(mid)返回为假，r = l，正常退出 对于这两个模板，不需要硬记，在做题的过程中边分析边写完全没问题，记住如果分析的过程中出现了“—”号，一定要在mid这里除以2的时候加1。可以告诉自己本身(l+r)/2就是下取整，有损失，这里又出现了减法，损失更大了，所以要写成(l+r+1)/2。 分巧克力 题目分析 希望巧克力的边长最大，而巧克力的边长要满足一个条件，就是按照该边长切出来的巧克力的块数应该大于等于K块才能满足K位小朋友都有巧克力。那么现在就是满足条件的最大值，我们要看一下他是否符合二段性，二分的关键在于二段性。 对于边长为mid的巧克力，如果它可以切出k块巧克力，那么我们可以确定边长小于mid的巧克力一定也可以，但是此时我需要找的是最大的边长，那么mid一定比小于mid的值更大，所以小于mid的值我就不用管了，也就是我可以确定我能够舍弃掉mid左边的值。我还想要确定比mid更大的边长是否也满足条件，所以我要在mid的右边继续二分。 对于边长为mid的巧克力，如果它不可以切出k块巧克力，那么我们可以确定边长大于mid的巧克力一定也不可以，所以大于等于mid的值我就不用管了，也就是我可以确定我能够舍弃掉mid右边的值。我还想要寻找比mid更小的边长是否能满足条件，所以我要在mid的左边继续二分。 综上该题满足二段性，可以用二分，二分的板子就不说了，接下来说一下check函数如何写。 check(u)要实现的作用是检查边长为u的情况下能否切出k块巧克力。已知某块巧克力为 W ∗ H W*H W∗H大小，那么能够切出来的巧克力个数用 ( W / u ) ∗ ( H / u ) (W/u)*(H/u) (W/u)∗(H/u)表示。注意不能用 ( W ∗ H ) / ( u ∗ u ) (W*H)/(u*u) (W∗H)/(u∗u)表示。那么只需要遍历当前每一块巧克力，求出能个切割的巧克力总数和k比较就可以了，代码如下， private static boolean check(int[][] a, int mid, int k) { int sum = 0; for (int i = 0; i < a.length; i++) { sum =sum + (a[i][0]/mid)*(a[i][1]/mid); } if(sum >= k) { return true; } return false; } 那么这里的边长的最小值是1，最大值就是巧克力的最大边长，也就是100000。 题目代码 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int k = scanner.nextInt(); int a[][] = new int[n][2]; for (int i = 0; i < n; i++) { a[i][0] = scanner.nextInt(); a[i][1] = scanner.nextInt(); } int l = 1; int r = 100000; while(l int mid = (l + r + 1) / 2; if(mid == 1) break; if(check(a,mid,k)) { l = mid; }else { r = mid - 1; } } System.out.println(l); } private static boolean check(int[][] a, int mid, int k) { int sum = 0; for (int i = 0; i < a.length; i++) { sum =sum + (a[i][0]/mid)*(a[i][1]/mid); } if(sum >= k) { return true; } return false; } } 求阶乘 题目分析 如果直接去求，我们看一下，K的范围已经到了 1 18 1^{18} 118，这么大肯定有什么巧妙的地方，而不是直接求解。对于一个数字N而言，我们怎么去求他的阶乘末尾包含0的个数？末尾的0是如何产生的？是不是由 2 ∗ 5 = 10 2*5=10 2∗5=10产生的？我们只需要求N！里面包含几个2或者几个5就行了，那么由2或者5个数的最小值决定末尾0的个数，那么2和5而言，比如1-20里面，5，10，15，20包含5，而2，6，8，10，12，14，16，20里面包含2，也就是5的个数必然比2少，那么只需要求N！里面包含5的个数就可以了。那么这个求法大家可以记住，代码如下， private static long f(long x) { long res = 0; while(x > 0) { res += x / 5; x = x / 5; } return res; } 求x！里面包含5的个数，令x/5，直到x的值为0就停止。比如25里面5的个数等于sum+=25/5=sum+=5。25/5=5不等于0，所以还要再来一次sum+=5/5=sum+=1。此时就可以了。那么25里面包含6个5。其中5，10，15，20，都包含1个5，而25里面两个5，所以一共6个5。 我们要求满足N！末尾0的个数恰好为K的最小的N是不是就是求满足条件的最小，还是要考虑一下二分。 如果对于mid！末尾0的个数比K少，那么所有比mid小的值的阶乘包含的5的个数肯定更少，所以我可以把mid左边的值都舍弃掉，继续向mid右边寻找。 如果对于mid！末尾0的个数比K大，那么所有比mid大的值的阶乘包含的5的个数肯定更多，所以我可以把mid右边的值都舍弃掉，继续向mid左边寻找。 综上满足二分的二段性，而check函数就是求解N！里面5的个数，前面已经讲解了。 但是注意这里，我不能确定一定可以找到一个满足条件的解，对于分巧克力那道题，题目说了每个小朋友能够至少获得一块边长为1的巧克力，所以边长为1一定满足条件，一定有解。而本题也说了，这样的N可能不存在，所以在二分结束后，我要确定一下，当前的值是否满足条件。 题目代码 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); long k = scanner.nextLong(); long l = 1,r = Long.MAX_VALUE-10; while(l < r) { long mid = (l+r)/2; if(f(mid) < k ) { l = mid + 1; }else { r = mid; } } if(f(l) == k) { System.out.println(l); }else { System.out.println(-1); } } private static long f(long x) { long res = 0; while(x > 0) { res += x / 5; x = x / 5; } return res; } } 相关阅读
您阅读本篇文章共花了：
发表评论