脚本宝典收集整理的这篇文章主要介绍了二分搜索法(分治策略典例),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
public static int seArch(int x,int arr[],int start,int end) { while (start <= end) { int mid = (start + end) / 2; if (x == arr[mid]) { return mid; } if (x <= arr[mid]) { start = mid + 1; } else end = mid - 1; } return -1;}
我的生日要到了!根据习俗,我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对,每个人会拿到一块派(必须一个派的一块,不能由几个派的小块拼成;可以是一整个派)。
我的朋友们都特别小气,如果有人拿到更大的一块,就会开始抱怨。因此所有人拿到的派是同样大小的(但不需要是同样形状的),虽然这样有些派会被浪费,但总比搞砸整个派对好。当然,我也要给自己留一块,而这一块也要和其他人的同样大小。
请问我们每个人拿到的派最大是多少?每个派都是一个高为1,半径不等的圆柱体。
第一行包含两个正整数N和F,1 ≤ N, F ≤ 10 000,表示派的数量和朋友的数量。 第二行包含N个1到10000之间的整数,表示每个派的半径。
输出每个人能得到的最大的派的体积,精确到小数点后三位。
3 3
4 3 3
在这里给出相应的输出。例如:25.133
解题思路:
如何想到二分法?
这个题目有个答案范围最大体积是所有体积相加,最小是零,那么我们就要在这个范围内找到能够均分给所有人且每人分得一样大小的最大值。总结:二分法题目1.答案有范围 2.求最值 3.有卡点条件
代码:
import java.util.Scanner;import static java.lang.StrictMath.acos;public class Java2_3 { public static void main(String[] args) { Scanner input = new Scanner(System.in); int N = input.nextInt(); int F = input.nextInt(); double[] R = new double[N]; //半径 final double PI = acos(-1.0); double[] V = new double[N];//体积 for (int i = 0; i < N; i++) { R[i] = input.nextDouble(); V[i] = Math.pow(R[i], 2) * PI; } double max = V[0]; double min = 0; double mid = 0; for (int i = 0; i < N; i++) { if (max < V[i]) { max = V[i]; //最大的体积 } } while(max-min>1e-5){ mid = (max+min)/2; //中间体积 二分法 if(ok(mid,V,N,F)) min=mid; //够分 就向右 else max=mid; //不够分 就向左 } String num = String.format("%.3f",mid); System.out.PRint(num); //输出最后可以分的体积 } public static Boolean ok(double s,double v[],int N,int F) { int poe = 0; for (int i = 0; i < N; i++) { poe += Math.floor(v[i] / s); //向下取整(是题目情况向下或向上)每个面积除以中间值面积 } if (poe >= (F + 1)) return true; //如果人数大于现有人数则可以分 else return false; }}
以上是脚本宝典为你收集整理的二分搜索法(分治策略典例)全部内容,希望文章能够帮你解决二分搜索法(分治策略典例)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。