当前位置: 代码迷 >> 综合 >> POJ3122 二分与误差
  详细解决方案

POJ3122 二分与误差

热度:4   发布时间:2024-01-16 13:59:47.0

题意:

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;
}