二分查找-POJ 3122-Pie

本文主要是介绍二分查找-POJ 3122-Pie，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接：Pie

题目大意：

有N张饼，k个朋友，为了体面，必须把饼切割成大小一样的k+1块（包括主人自己），求出每个人能得到的最大饼体积。

前提：每人一块，饼可以有剩余

二分去暴力答案，确定下界为0，上界为最大体积的饼（每人一块，最大可能就是饼的体积都相等，也就是每块都是最大值）。

代码：

#include<stdio.h>
#include<math.h>
#define MAX_SIZE 100005
#define max(a,b) (a>b?a:b)
#define Pi acos(-1.0)    //圆周率
#define eps 1e-6double Volume[MAX_SIZE];
int main()
{int t;scanf("%d",&t);while(t--){int N,F,ri;while(~scanf("%d%d",&N,&F)){//printf("%lf\n",Pi);double Max=-1;for(int i=0;i<N;i++){scanf("%d",&ri);Volume[i]=ri*ri*Pi;Max=max(Max,Volume[i]);    //求出最大体积的Pie}double l=0.0,r=Max;double Mid;while(r-l>eps){Mid=(l+r)/2;int cnt=0;for(int i=0;i<N;i++)cnt+=(int)(Volume[i]/Mid);    //按mid切割（取整）if(cnt>=F+1)    //能分配的人大于F+1，往上取值l=Mid;elser=Mid;}printf("%.4lf\n",Mid);}}return 0;
}

 

这篇关于二分查找-POJ 3122-Pie的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---