本文主要是介绍HDU 1969 Pie (二分查找)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：click here~~
题目大意：n块馅饼分给m+1个人，每个人的馅饼必须是整块的，馅饼可以被切开，但不能组合，也不一定要全部分完,问你每个人最大能分到多大体积的馅饼面积。
【解题思路】：二分，对于每个V值，我们枚举对应情况下人数P的多少，发现是单调递减的，因此二分查找区间，初始值left=0,right=inf;然后judge函数判断当前mid值能否使得p>=m,因此累计ans=num[i]/mid,写的时候二分用的是while判断，怎么调试答案就是差了那么一点点。后来索性改成for循环，结果立刻就出来了，看来有时候实在不知道那错了，换一种写法可能就对了
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
const int inf=1e10;
const int eps=1e-6;
const double pi=acos(-1.0);
double num[N];
int n,m;
bool get(double mid)
{int ans=0;for(int i=1; i<=n; i++){ans+=(int)floor(num[i]/mid);}return ans>=m;//确保m+1个人每人都能得到最大面积
}
int main()
{//freopen("1.txt","r",stdin);int t,tot=1;scanf("%d",&t);while(t--){double c,sum=0,maxx=0;scanf("%d%d",&n,&m);m+=1;for(int i=1; i<=n; i++){scanf("%lf",&c);num[i]=c*c*pi;}double ll=0,rr=inf;//printf("ll==%.4lf rr==%.4lf\n",ll,rr);for(int i=1;i<=100;i++){double mid=(ll+rr)/2;if(get(mid)) ll=mid;else rr=mid;}// printf("%.4f\n",mid);printf("%.4f\n",ll);// printf("%.4f\n",rr);}return 0;
}
/*
Sample Input
3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2
Sample Output
25.1327 3.1416 50.2655
*/
这篇关于HDU 1969 Pie (二分查找)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
