UVA12097 Pie

发布于 2020-08-16  1.36k 次阅读


题面

题意

这里有 $n$ 个派,$f+1$ 个人(由于题面中说有 $f$ 个朋友,加上我自己,一共是 $f+1$ 个人)需要平分这些派,每个人分到的面积必须相同,并且每个人分到的都必须是一整块(原来的派可以切开)。

解法

简单二分答案,二分每个人分到的派的面积。其中 check 函数的功能是对于你找出的每个人分得的派的面积,求出一共能切出几块这样的派。详情见代码。

代码

#include <bits/stdc++.h>
using namespace std;

int n, f;
double area[10005];

bool check(double s) {  //返回当每个人分到的面积为s时能分出来的块数
    int tot = 0;
    for (int i = 1; i <= n; i++)
        tot += floor(area[i] / s);
    return tot >= f;
}

int main() {
    double pi = acos(-1);
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &f);
        f++;
        double l = 0, r = 0;
        for (int i = 1; i <= n; i++) {
            double t;
            cin >> t;
            area[i] = (double)t * t * pi;
            r = max(r, area[i]);
        }
        while (l <= r) {//二分每个人分到的面积
            double mid = (l + r) / 2;
            if (check(mid))
                l = mid + 0.00001;
            else
                r = mid - 0.00001;
        }
        printf("%.4lf\n", check(l) ? l : r);
    }
    return 0;
}

我缓慢吐出一串啊吧啊吧并不再想说话