计蒜客题解

计蒜客，https://nanti.jisuanke.com/t/T1157。

我的OJ，http://47.110.135.197/problem.php?id=4951。

我的生日要到了！根据习俗，我需要将一些派分给大家。我有 N 个不同口味、不同大小的派。有 F 个朋友会来参加我的派对，每个人会拿到一块派（必须一个派的一块，不能由几个派的小块拼成；可以是一整个派）。 我的朋友们都特别小气，如果有人拿到更大的一块，就会开始抱怨。因此所有人拿到的派是同样大小的（但不需要是同样形状的），虽然这样有些派会被浪费，但总比搞砸整个派对好。当然，我也要给自己留一块，而这一块也要和其他人的同样大小。 请问我们每个人拿到的派最大是多少？每个派都是一个高为 1，半径不等的圆柱体。

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

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

有 N 个大小不同的派，要在 F 个朋友间分。要求大家分得一样多，而且不能有不同的派拼接起来。

OK，从这个要求可以看出，这是一题浮点数二分查找的模板题。因此我们的核心问题是要确定以下几个细节：

1、找到二分查找的左边界 left 和右边界 right；

2、合适的 check() 函数。

那么这个问题就可以套用浮点数二分查找模板来解决。

样例输入数据为如上。表示一共有 N=3 个派，F=3 个朋友分。3 个派的半径分别为 4,3,3 。

1、左边界和右边界分析。题目要求精确到小数点后三位，因此 PI 可以取 3.14159，结束精度可以选1e-5。那么这 3 个派对应的体积为 50.26544、28.27431、28.27431。

2、check() 函数。使用 mid 作为分配方案，检查是否满足分配条件。分配条件有两个：不能拼接，要超过 F+1 份（兄弟，你自己也要吃派的，所以是 F+1 份，这里是本题最大的坑）。

根据题目要求，每个人的派必须一样大，而且不能拼接。因此右边界为最大值 50.26544（为什么不能用最小值来做右边界？这个问题很容易回答，这样一个数据：2个派，1个朋友参加，第一个派半径为 5，第二个派的半径为 1），左边界为 0（有可能没有分配方案）。下面我们来模拟一下整个过程。整个二分查找如下表：

这样，我们最终的答案就是左边界，也就是 25.133（保留三位）。因此从上表的过程来看，题目要求三位，EPS 取 1e-5 是完全可以保证精度的。

1、PI 的定义。可以根据每题的精度要求进行定义。也可以参考https://blog.csdn.net/justidle/article/details/104620668，使用标准定义。

2、实际分派的人数是 F+1，而不是 F。要吧自己算上。大坑啊。

3、右边界必须用派的最大体积。而不能用最小体积。

4、精度 EPS 的定义。一般根据每题的精度要求，经验上说，只要比题目精度多两位即可。

1、读入数据，并找到最大的派，使用这个作为右边界。使用 0 作为左边界。

2、套用标准浮点数二分查找模板进行查找。

3、check 函数是用 mid 作为分配方案，看能否满足 F+1 个人分。如果可以，则缩小 mid 继续尝试；如果不可以，则扩大 mid 继续尝试。

1、PI 的定义。可以将 PI 定义为 3.14159，根据本题保留三位小数点要求。但是还是推荐例程中的定义方法。

2、check函数中。num 必须定义为整型，我们充分利用了 C++ 的数据类型转换这个知识点。

。