可以看出,达到最大size的时候一定是某个蛋糕刚好被分完,如果再大一点的话,肯定就不能解决了。
比这个size小,则无论如何都可以解决。
所以可以通过二分答案的方法来解决这个问题。就很简单了。
注意:这题精度要求很高,pi的值需要通过acos(-1)来求,eps要到e-5。
我用C++提交能够AC,g++一直WA。
吗的,数据能不能宽容点。
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int N, F;
double pi = acos(-1.0);
double pie[10032];
double sum, maxp;
int main()
{
double l, r, m;
int i, t, c;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &N, &F);
F++;
maxp = sum = 0;
for (i = 0; i < N; i++) {
scanf("%d", &c);
pie[i] = c*c*pi;
maxp = max(maxp, pie[i]);
sum += pie[i];
}
l = maxp / F;
r = sum / F;
while (l + 0.00001 < r) {
m = (l + r) / 2;
c = 0;
for (i = 0; i < N; i++)
c += floor(pie[i] / m);
if (c < F)
r = m;
else
l = m;
}
printf("%.4lf\n", l);
}
return 0;
}