「题解」派

你感受过被疯狂卡精度的恐惧吗……

一 题目

原题链接

描述

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

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

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

输入

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

输出

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

---

二 题解

先分析这个“派的体积”。柱体体积公式$v=sh$，其中底面积$s=\pi r^2$，故$v=\pi r^2h$。

再继续分析。若当前确定的派的体积为$v_1$，半径为$r_1$；并且存在一个原体积为$v_2$,半径为$r_2$的派。那么当前这个派可以被切成$\dfrac{v_1}{v_2}$块，也就是可以分给$\dfrac{v_1}{v_2}$个人。

分析这个$\dfrac{v_1}{v_2}$，有$\dfrac{v_1}{v_2}=\dfrac{\pi r_1^2 h_1}{\pi r_2^2 h_2}$。因$h_1=h_2=1$，上述分式可简化成$\dfrac{v_1}{v_2}=\dfrac{r_1^2}{r_2^2}$，也就是说一个派被分成的块数仅与当前确定的$r_1^2$有关（注意是平方）。

那么可以二分这个$r_1^2$，再计算面积即可。为什么不直接二分体积？体积是带着$\pi$的，一定会是一个浮点数（小数）。二分本来就有精度折损，因此二分体积可能会带来极大的精度问题。

但是本题疯狂卡精度！！既卡最终得数的精度，甚至还卡$\pi$的精度！
真是丧心病狂…
解决方法：对于最终得数，用long long储存$r_2$，并且每个$r^2$都乘上1e4以避免精度问题。虽然题面说保留三位小数，但并不代表乘上1e2就能避免被卡！对于$\pi$，在定义的时候令pi=acos(-1.0)即可。注意要引用cmath（即c中的math.h）库。

代码如下：

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

#define LL long long

const int CN=1e4+4;
const double pi=acos(-1.0);

LL read(){
    LL s=0,ne=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
    for(;c>='0'&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';
    return s*ne;
}

//v define
LL n,m,_r[CN];

LL l=0,r,mid;

LL calc(LL k){
    LL sum=0;
    for(int i=1;i<=n;i++)
        sum += _r[i]/k;
    return sum;
}

int main()
{
    n=read(); m=read(); m+=1;
    for(int i=1;i<=n;i++){
        _r[i]=read();
        (_r[i]*=_r[i])*=10000; //精度
        r = max(r, _r[i]);
    }
    
    while(l < r){
        mid = (l+r+1)>>1; //强制上取整，避免死循环
        if(calc(mid) >= m) l = mid;
            else r = mid-1;
    }
    
    double v=(pi*l)/10000.0;
    
    printf("%.3lf",v);
    
    return 0;
}