2025年计蒜客题解——T1157：派

大家好，我是讯享网，很高兴认识大家。

题目相关

题目链接

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

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

题目描述

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

输入格式

输出格式

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

样例输入

3 3 4 3 3

讯享网

样例输出

讯享网25.133

数据范围

1 ≤ N, F ≤ 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（有可能没有分配方案）。下面我们来模拟一下整个过程。整个二分查找如下表：

	left	right	mid	可以分几块	EPS
1	0	50.26544	25.13272	4	50.26544
2	25.	50.26544	37.69908	1	25.13272
3	25.	37.69908	31.41590	1	12.56636
4	25.	31.41590	28.27431	3	6.
5	25.	28.27431	26.	3	3.
6	25.	26.	25.	3	1.
7	25.	25.	25.	3	0.
8	25.	25.	25.	3	0.
9	25.	25.	25.	3	0.
10	25.	25.	25.	3	0.
11	25.	25.	25.	3	0.049087
12	25.	25.	25.14499	3	0.024543
13	25.	25.14499	25.	3	0.012272
14	25.	25.	25.	3	0.006136
15	25.	25.	25.	3	0.003068
16	25.	25.	25.	3	0.001534
17	25.	25.	25.	3	0.000768
18	25.	25.	25.	3	0.000383
19	25.	25.	25.	3	0.000191
20	25.	25.	25.	3	9.587e-5
21	25.	25.	25.	3	4.794e-5
22	25.	25.	25.	3	2.397e-5
23	25.	25.	25.	3	1.198e-5
24	25.	25.			5.99e-6

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

关键点

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

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

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

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

编程思路

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

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

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

AC 参考代码

讯享网#include <bits/stdc++.h> using namespace std; const double PI=acos(-1.0); const int MAXN = 1e4+6; double a[MAXN] = {};//每个派的体积 int n,f; bool check(double x) { int num=0;//本次按x作为半径可以分配的数量 for (int i=0; i<n; i++) { num+=a[i]/x;//充分利用数据类型转换 if (num>=f+1) { return true; } } return false; } int main() { //读入数据 scanf("%d%d", &n, &f); double right = 0; double left = 0; for (int i=0; i<n; i++) { scanf("%lf", &a[i]); a[i] = PI*a[i]*a[i];//计算出每个派体积 right = max(right, a[i]);//更新右边界 } //二分查找 const double EPS = 1e-5; double mid; while (right-left>EPS) { mid = (left+right)/2; if (check(mid)) { //可以分 left=mid; } else { right=mid; } } printf("%.3lf\n", left); return 0; }

关键代码说明

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

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

时间复杂度

O(n*logn) 。