分蛋糕问题

69 阅读 0 评论 46 点赞

我是靠谱客的博主有魅力鸡翅，最近开发中收集的这篇文章主要介绍分蛋糕问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：作者要开一个生日party，他现在拥有n块高度都为1的圆柱形奶酪，已知每块奶酪的底面半径为r不等，
作者邀请了f个朋友参加了他的party，他要把这些奶酪平均分给所有的朋友和他自己（f+1人），
每个人分得奶酪的体积必须相等（这个值是确定的），形状就没有要求。
现在要你求出所有人都能够得到的最大块奶酪的体积是多少？

要求是分出来的每一份必须出自同一个pie，也就是说当pie大小为3，2，1，只能分出两个大小为2的，
剩下两个要扔掉。

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.

#include<stdio.h>

int n,r,f,i,max;
double p[10050];
#define pi 3.1415926535897932
int judge()
{int left=0,right=max;
double mid;
while(right-left>0.000001){
double sum=0;
mid=(left+right)*1.0/2;
for(i=0;i<n;i++)
{
sum=sum+p[i]/mid;
if(sum>f)
left=mid;
else
right=mid;
}
}
return mid;
}
此题主要是利用二分法找最大的体积，二分法查找

int main()
{int t,r;
scanf("%d",&t);
while(t--)
{
max=0;
scanf("%d",&f);
f=f+1;
for(i=0;i<n;i++)
{
scanf("%d",&r);
p[i]=pi*r*r;
if(max<p[i])
max=p[i];
}
printf("%.4lf",judge());

}
return 0;
}