题目链接

题目大意:

有n个蛋糕,每个蛋糕有个半径。我们需要把这些蛋糕分给F + 1个人。F+1个人分得得蛋糕的大小必须

是一样的(形状可以不一样)。分得的蛋糕可以由原来的蛋糕切割下来的,但不能是由几个蛋糕拼凑而成。

求如何切才能使分得的蛋糕大小最大。只用输出最后分得的蛋糕的面积即可

大致思路:

我们可以二分这个最大对蛋糕面积。然后把它带入切蛋糕的过程。

求出如果这个面积是正确答案,我们能切出几块蛋糕。

如果切出的蛋糕比F+1大,说明这个值小了。

如果切出的蛋糕比F+1小,说明这个值大了。

代码如下:

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#define mmset(a,b) memset(a,b,sizeof(a))
#define ll long long
using namespace std;
const double PI = acos(-1);
const double esp = 1e-6;
const int N = 1e4 + 5;
double data[N];
int n,k;

int count1(double a);

/*
3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2
Sample Output
25.1327
3.1416
50.2655
*/
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d",&n, &k);
		k++;
		for(int i = 1; i <= n; i++)
		{
			scanf("%lf",&data[i]);
			data[i] = data[i] * data[i] * PI;
		}
		sort(data + 1, data + 1 + n);
		double a = 0,b = 1e4 * 1e4 * 2 * PI,m;
		while(b - a >= esp)
		{
			m = (a + b) / 2.0;
			if(count1(m) >= k)
			{
				a = m;
			}
			else
			{
				b = m;
			}
		}
		printf("%.4f\n",a) ;
		
	}
	
	
	return 0;
}
int count1(double a)
{
	int sum = 0;
	for(int i = 1; i <= n; i++)
	{
		sum += (int)(data[i] / a);
	}
	return sum;
}