问题描述
问题分析
二分思想的运用
通过最大值到0的不断二分逼近
来寻找可能的最大值
有别于二分查找在数组中找某一个数
这里不需要对数组进行排序
因为判断的是当前mid可以分的个数
如果分的少了 说明需要小些
反之则说明可以大一些
如此循环则可以不断逼近正确结果
其它需要注意的就是需要注意
数据精度问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #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