题面翻译
题目描述
有$F+1$个人来分$N$个圆形派,每个人得到的必须是一整块派,而不是几块拼在一起。而且派的面积要相同。求每个人最多得到多大面积的派(不必是圆形)
输入格式
输入的第一行为数据组数$T$.每组数据的第一行为两个整数$N$和$F(1<=N,F<=10000);$第二行为N个整数$r_i(1<=r_i<=10000)$,即各个派的半径。
输出格式
对于每组数据,输出每个人得到的派的面积的最大值,精确到$10^{-3}$
Translated by @洛谷万岁
题目描述
输入格式
输出格式
样例 #1
样例输入 #1
3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2
样例输出 #1
25.1327
3.1416
50.2655
算法1
(二分) $O(log_2n)$
二分体积大小$V$,当$V$满足条件:所有派按$V$进行切割,得到的数量$\ge f+1$,即可放大体积$V$,否则缩小体积$V$
时间复杂度
二分时间复杂度为$O(log_2n)$
参考文献
《算竞》
Python 代码
from math import pi
t=int(input())
def check(x):
global f
cnt=0
for i in range(n):
cnt+=a[i]//x
return cnt>=f+1
def bisearch():
global maxx
l=0
r=maxx
eps=1e-4
while r-l>eps:
mid=(l+r)/2
if check(mid):
l=mid
else:
r=mid
return l
for i in range(t):
n,f=map(int,input().split())
a=list(map(int,input().split()))
maxx=0
for i in range(n):
a[i]=pi*a[i]**2
maxx=max(maxx,a[i])
print('{:.4f}'.format(bisearch()))