题意:有F+1个人来分N个圆形派,要求每个人得到的派必须是一整块的,不能是几块拼在一起的,而且每个人得到的派的大小一样,问每个人最多能得到的派的面积。
思路:一开始拿到题目,我尝试推公式,后来觉得实在找不到规律,看了书,发现是二分答案,把问题转化为“是否可以让每个人的到面积为x的派”。因为派是不可以拼起来的,所以每个派可以分到[PI*r^2 / x]个派,把每个派可以分出的块加起来看是否>=F+1就好了。
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const double PI = acos ( -1.0 ) ; const int maxn = 10005 ; int n, F, T; double s[ maxn ],maxS; bool candiv(double x) { int sum = 0; for( int i=0 ; i < n ; ++i ) sum += s[i]/x; if(sum >= F + 1 ) return 1; return 0; } int main() { scanf("%d", &T); while(T--) { scanf( "%d %d", &n , &F ); maxS=0.0; for( int i=0 ; i < n ; ++i ) { scanf( "%lf" , &s[i] ); s[i] = PI * s[i] * s[i]; maxS = max ( maxS , s[i] ); } double low = 0.0 , high = maxS; while( high - low > 1e-5 ) { double mid = (high + low) / 2.0 ; if(candiv(mid)) low = mid ; else high = mid; } printf("%.4lf\n", low ); } }