派（二分答案）

05:派

总时间限制: 

1000ms

 

内存限制: 

65536kB

描述

我的生日要到了！根据习俗，我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对，每个人会拿到一块派（必须一个派的一块，不能由几个派的小块拼成；可以是一整个派）。

我的朋友们都特别小气，如果有人拿到更大的一块，就会开始抱怨。因此所有人拿到的派是同样大小的（但不需要是同样形状的），虽然这样有些派会被浪费，但总比搞砸整个派对好。当然，我也要给自己留一块，而这一块也要和其他人的同样大小。

请问我们每个人拿到的派最大是多少？每个派都是一个高为1，半径不等的圆柱体。

输入

第一行包含两个正整数N和F，1 ≤ N, F ≤ 10 000，表示派的数量和朋友的数量。
第二行包含N个1到10000之间的整数，表示每个派的半径。

输出

输出每个人能得到的最大的派的体积，精确到小数点后三位。

样例输入

3 3
4 3 3

样例输出

25.133
【思路】刘汝佳蓝本上的题目
一开始我是没想到用二分答案，虽然这些题都是二分答案类型的，（当你做一道题目时，你不能正在学什么就往什么方面考虑，你要想，用什么方法为什么用这个方法）但是没有标志性的
最小值最大的问法。然后我看了看题解。。。。。。 
介绍一下蓝本的思路：每个人分最多分所有派里面积最大的，要么无限小（这是答案范围）；卡答案的条件就是能不能分得到，显然是用二分答案的
所以 二分答案的题目 比较直接的问法 最小值最大 一看就是二分答案了，但是比较隐形的问法 首先要看看有这么几个特点1 能确定答案范围 2有卡答案的条件
orz 
【代码】

#include<iostream>
#include<cstdio> 
#include<cstdlib>
#include<iomanip>
#include<cmath>
using namespace std;
const double pi=acos(-1.0);// acos(-1.0)就是求-1.0的反余弦，经计算，acos(-1.0) 的值就是圆周率 
const int MAXX=100009;
double a[MAXX];
bool ok(double);
int n,f;
int main()
{
    int T;
    double maxx=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&f);
        for(int i=0;i<n;i++)
        {
            int r;
            scanf("%d",&r);
            a[i]=pi*r*r;//每个派的面积 
            maxx=max(maxx,a[i]);//max函数里的变量类型相同 ，都是double 
        }
        double l=0,r=maxx;
        while(r-l>1e-5)//精确 二分答案的套路过程 
        {
            double m=(l+r)/2;
            if(ok(m))l=m;//扩大范围，看看每个人能不能分到更多 
            else
            r=m;
        }
        printf("%.3lf",l);//printf格式化输出会自动四舍五入； 
    }
    return 0;
}
bool ok(double s)//每人是否能分面积s的派 
{
    int sum=0;
    for(int i=0;i<n;i++)
    {
        sum+=floor(a[i]/s);//向下取整，分不到s的浪费； 
    }
    return sum>=f+1;//能否分到 
}