分f个派给n+1(n个朋友和自己)个人 要求每一个人分相同面积 但不能分到超过一个派 即最多把一整个派给某个人 问能平均分的最大面积
二分平均面积 下界0 上界最大的一份派的面积 推断条件从大派開始分(保证尽量满足)假设能分出n+1份 这样的分法就合适 下界上移 最后输出下界就可以 注意二分推断上下界用esp 否则超时
从大到小分派是一种贪心策略 太小的派能够扔掉 但从小開始分有可能第一个派就分不出这么大 不排序也可遇到小派跳过 最后推断
代码例如以下:
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define PI 3.141592653589793 #define esp 1e-4 using namespace std; int r[10000]; int n,f; bool cmp(int a,int b)//从大到小排 贪心策略找最优 { return a >b; } bool can(double x) { int i,ans = 0; double cnt,sz; for(i = cnt = 0; i < f; ++i,cnt = 0) { sz = r[i]*r[i]*PI; while(sz-cnt-x>esp)//不断从同一份上割 知道不能切割为止 { if(ans == n) return true;//已分出n份时 这份是给自己的 即已分完 cnt += x; ans++; } } return false;//有人没分到 false } int main() { int t,i; double low,high,mid; scanf("%d",&t); while(t--) { scanf("%d %d",&f,&n); low = high = 0; for(i = 0; i < f; ++i) { scanf("%d",&r[i]); if(r[i] > high) high = r[i]; } high = high*high*PI; sort(r,r+f,cmp);//排序保证最优解 while(high - low > esp)//二分找最大 { mid = (high+low)/2; if(can(mid)) low = mid; else high = mid - 0.0001; } printf("%.4f ",low); } return 0; }