NOI OpenJudge 题库 8211 派

描述

我的生日要到了!根据习俗,我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对,每个人会拿到一块派(必须一个派的一块,不能由几个派的小块拼成;可以是一整个派)。

我的朋友们都特别小气,如果有人拿到更大的一块,就会开始抱怨。因此所有人拿到的派是同样大小的(但不需要是同样形状的),虽然这样有些派会被浪费,但总比搞砸整个派对好。当然,我也要给自己留一块,而这一块也要和其他人的同样大小。

请问我们每个人拿到的派最大是多少?每个派都是一个高为1,半径不等的圆柱体。

输入

第一行包含两个正整数N和F,1 ≤ N, F ≤ 10 000,表示派的数量和朋友的数量。
第二行包含N个1到10000之间的整数,表示每个派的半径。

输出

输出每个人能得到的最大的派的体积,精确到小数点后三位。

样例输入

1
2
3 3
4 3 3

样例输出

1
25.133

分析

先由半径求体积,而后二分查找,区间为(0,最大的单个派的体积)。

个人 WA 的原因:

  • π 的值一开始取 3.141569 ,小数点后 6 位,这样的精度居然还不够,可以用 math 库中的反余弦函数 acos(-1.0)
  • check 函数中表示当前能够分的块数的变量 sum 要用 int

代码

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
39
40
41
#define loop(i,n) for(int i=0;i<n;i++)
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n,f;
double a[10010];
const double PI=acos(-1.0);
int check(double x)
{
int sum=0;
loop(i,n)
{
sum+=a[i]/x;
if(sum>=f)
return 1;
}
return 0;
}
int main()
{
double left=0,right=0,mid;
cin >>n>>f;
f++;
loop(i,n)
{
cin >>a[i];
a[i]=a[i]*a[i]*PI;
if(a[i]>right)
right=a[i];
}
while(right - left>0.000001)
{
mid=(left+right)/2;
if(check(mid))
left=mid;
else right=mid;
}
printf("%.3lf\n",left);
return 0;
}
分享到 评论