【PTA】二分搜索 7-3 派 (30 分)

痛定思痛。 2022-09-12 04:57 58阅读 0赞

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

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

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

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

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

**输入样例:**

3 3
    4 3 3
    结尾无空行

**输出样例:**  
在这里给出相应的输出。例如：

25.133
    结尾无空行

题解：

#include<bits/stdc++.h>
    using namespace std;
    int n,f;
    const double PI=acos(-1.0);
    double a[10005];
    bool judge(double s)
    {
        
    	int count=0;
    	for(int i=0;i<n;i++)
    	{
        
    		count+=floor(a[i]/s);
    	}
    	return count>=f+1;
    }
    int main()
    {
        
    	cin>>n>>f;
    	double smax=0,low=0,mid=0;
    	for(int i=0;i<n;i++)
    	{
        
    		cin>>a[i];
    		a[i]=PI*a[i]*a[i];
    		smax=max(a[i],smax);
    	} 
    	while(smax-low>1e-5)
    	{
        
    		mid=(smax+low)/2;
    		if(judge(mid))
    		{
        
    			low=mid;
    		}
    		else
    		{
        
    			smax=mid;
    		}
    	}
    	cout<<fixed<<setprecision(3)<<low;
    	return 0;	
    }