题意:
n个派f+1个人分(包括自己),同一个派可以分成多块,但每个人只能拿一块,并且不能拼接比如一块6派,如果拿5,剩下的1就得丢弃
要点:
1.比较普通的二分,将每块派大小除mid,累加得到分给的人数。要注意mid也就是每个人分到的派可以是浮点数。
2.要求精度问题,因为left和right都是double型,mid=(left+right)/2,所以这两个只能无限接近。因为最后答案都是小数点后4位,所以right-left的精度要求可以是五位或更多。
| 15084821 | Seasonal | 3122 | Accepted | 256K | 47MS | C++ | 675B | 2016-01-19 21:48:50 |
代码如下:
#include<stdio.h>
#define maxn 10005
#define pi 3.1415926535897932 //π的精度也要足够高int main()
{int cas;scanf("%d", &cas);while (cas--){int n, f,i;double a[maxn]; //为了精度必须doubledouble step,sum=0;scanf("%d%d", &n, &f);f++; //自己也要包括进去for (i = 1; i <= n; i++){scanf("%lf", &a[i]);a[i] *= a[i];sum += a[i];}double left = 0;double right = sum / f;while (right - left> 0.000001)//接近到要求的精度即可,因为答案是小数点后4位,取1e-5{double mid = (left + right) / 2;int num=0;for (i = 1; i <= n; i++)num +=(int) a[i] / mid;if (num < f)right = mid; //因为left和right都是浮点数,最后肯定不会相等,只能无限接近else{left = mid; //不用对+1或-1操作step = mid;}}printf("%.4lf\n", step*pi);}return 0;
}