【题解】LA 3635【Pie】

分析

二分答案,将问题转化为“是否可以让每个人得到一个面积为$x$的派”。这样就多了一个条件,然后求解目标就成了“这些条件是否矛盾”。
显然只有一种矛盾:$x$太大,不够人分了。这样只需计算可以切成多少份面积为$x$的派,然后看看这个数目够不够人数即可。

代码

#include<cstdio>
#include<algorithm>
using std::max;
const double PI = 3.1415926535897932384626433832795028841971;
const double eps = 1e-6;
const int MAXN = 10000 + 6;

int n,f;
double A[MAXN];

bool ok(double area){
    int sum = 0;
    for(int i = 0;i < n;i++) sum += (long long)(A[i] / area);
    return sum >= f + 1;
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&f);
        double maxa = -1;
        for(int i = 0;i < n;i++){
            int r;scanf("%d",&r);
            A[i] = PI * r * r;maxa = max(maxa,A[i]);
        }
        double L = 0,R = maxa;
        while(R - L >= eps){
            double M = (L + R) / 2;
            if(ok(M)) L = M;
            else R = M;
        }
        printf("%.5f\n",L);
    }

    return 0;
}