GitBook

这里写图片描述

二分思想的运用 通过最大值到0的不断二分逼近 来寻找可能的最大值

有别于二分查找在数组中找某一个数 这里不需要对数组进行排序 因为判断的是当前mid可以分的个数 如果分的少了 说明需要小些 反之则说明可以大一些 如此循环则可以不断逼近正确结果

其它需要注意的就是需要注意 数据精度问题

#include<stdio.h>
#include<math.h>
//#include<algorithm>
//using namespace std;
double pi=acos(-1.0);
double a[10020];
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		int n,m;
		scanf("%d %d",&n,&m);
		m++;
		double sum=0;
		for(int i=0; i<n; i++) {
			int t;
			scanf("%d",&t);
			a[i]=t*t;
			sum+=a[i];
		}
//		sort(a,a+n);
//	非常好的一点 这种方式其实不用排序
		double lt=0,rt=sum/m,mid;
		while(rt-lt>0.000001) {
			mid=(lt+rt)/2;
			int cnt=0;
			for(int i=0; i<n; i++) {
				cnt+=(int)(a[i]/mid);
			}
			if(cnt>=m)
				lt=mid;
			else
				rt=mid;
		}
		printf("%.4lf\n",mid*pi);
	}
	return 0;
}

题目地址: 【POJ】[3122]Pie 【杭电】[1969]Pie