HDU1969Pie：运用二分查找算法优化解决方案

题目大意是要办生日Party&＃xff0c;有n个馅饼&＃xff0c;有f个朋友。接下来是n个馅饼的半径。然后是分馅饼了&＃xff0c;
注意咯自己也要&＃xff0c;大家都要一样大&＃xff0c;形状没什么要求&＃xff0c;但都要是一整块的那种&＃xff0c;也就是说不能从两个饼中
各割一小块来凑一块&＃xff0c;像面积为10的和6的两块饼&＃xff08;饼的厚度是1&＃xff0c;所以面积和体积相等&＃xff09;&＃xff0c;
假设每人分到面积为5&＃xff0c;则10分两块&＃xff0c;6切成5。够分3个人&＃xff0c;假设每人6。则仅仅能分两个了&＃xff01;
题目要求我们分到的饼尽可能的大&＃xff01; 仅仅要注意精度问题就能够了,一般WA 都是精度问题

运用2分搜索&＃xff1a;

首先用总饼的体积除以总人数&＃xff0c;得到每一个人最大能够得到的V&＃xff0c;可是每一个人手中不能有两片或多片拼成的一块饼。

最多仅仅能有一片切割过得饼。

用2分搜索时。把0设为left。把V 设为right。mid&＃61;(left&＃43;right)/2;

搜索条件是&＃xff1a;以mid为标志&＃xff0c;假设每块饼都能够切割出一个mid。那么返回true,说明每一个人能够得到的饼的体积能够

大于等于mid;假设不能分出这么多的mid,那么返回false,说明每一个人能够得到饼的体积小于等于mid。

&＃xff08;1&＃xff09;精度为&＃xff1a;0.000001

(2) pi 用反余弦求出&＃xff0c;精度更高。

#include
#include
#include
using namespace std;
double pi &＃61; acos(-1.0);
int F,N;
double V[10001];
bool test(double x){int num&＃61;0;for(int i&＃61;0;i&＃61;F) return true;else return false;
}
int main()
{int t,r;double v,max,left,right,mid;scanf("%d",&t);while(t--){scanf("%d%d",&N,&F);F &＃61; F &＃43; 1;for(int i&＃61;0;i 1e-6){mid &＃61; (left &＃43; right) / 2;if(test(mid)) left &＃61; mid;else right &＃61; mid;}printf("%.4lf\n",mid);}return 0;
}