NOI OpenJudge 题库 8211 派

Algorithms
NOI OpenJudge, 二分

描述

我的生日要到了！根据习俗，我需要将一些派分给大家。我有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;
}
分享到