HDU 1969 Pie

Description

My birthday is coming up and traditionally I’m serving pie. Not just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming to my party and each of them gets a piece of pie. This should be one piece of one pie, not several small pieces ……

题目链接

Input

One line with a positive integer: the number of test cases. Then for each test case: —-One line with two integers N and F with 1 <= N, F <= 10 000: the number of pies and the number of friends. —-One line with N integers ri with 1 <= ri <= 10 000: the radii of the pies.

Output

For each test case, output one line with the largest possible volume V such that me and my friends can all get a pie piece of size V. The answer should be given as a floating point number with an absolute error of at most 10^(-3).

Sample Input

3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2

Sample Output

25.1327

3.1416

50.2655

题意

n块同高（为1）不同半径的“派”平均分给f + 1个人，每个人分到的蛋糕必须来自同一块

思路：二分

二分三大要素：上限、下限（多数为0）、bool judge（）函数

上限：每块派都近乎完美，那样答案是所有的体积的和 / 人数

下限：0

judge（mid）函数：遍历每块派，他们的体积 / mid 取整的和 >= 人数即满足条件

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const double pi = acos(-1.0);
int n, f;
double a[10005];

bool judge(double x)
{
    int tot = 0;
    for(int i = 0; i < n; ++i)
        tot += int(a[i] / x);
    if(tot >= f)
        return 1;
    return 0;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        memset(a, 0, sizeof(a));
        cin >> n >> f;
        f++;
        double sum = 0;
        for(int i = 0; i < n; ++i)
        {
            scanf("%lf", &a[i]);
            a[i] *= a[i];///同高时体积可看成底面积，pi可忽略（最后算上）
            sum += a[i];
        }
        double left = 0, right = sum / f;
        while(right - left > 0.000001)///double卡精度
        {
            double mid = (left + right) / 2;
            if(judge(mid))
                left = mid;
            else
                right = mid;
        }
        printf("%.4f\n", right * pi);
    }
    return 0;
}