标题:做题送分啦,10分(加油!)
只看楼主
op123
Rank: 6Rank: 6
等 级:贵宾
威 望:21
帖 子:170
专家分:461
注 册:2022-6-4
结帖率:100%
已结贴  问题点数:10 回复次数:5 
做题送分啦,10分(加油!)
2204 - 【基础】生日馅饼

题目描述
我的生日快到了,我们这有过生日做馅饼的传统。我朋友们要来参加我的生日宴会,他们每人将会得到一块馅饼。
这应该是一个馅饼的一块,而不是几个小块。不过,这一块也可以是一整块馅饼。我的朋友们都很讨厌,如果他们中的一个分到的比其他人更多,他们就会开始抱怨。
因此,所有的馅饼都应该得到同样大小(但不一定是同样形状)的馅饼,即使这会导致一些馅饼变质(这比破坏聚会要好)。
当然,我自己也要有一块馅饼,而且那块馅饼也应该一样大。
我们能得到的最大可能的尺寸是多少?所有的馅饼都是圆柱形的,它们都有相同的高度1,但是馅饼的半径可以不同。

输入
第一行正整数m,表示测试的数量。对于每个测试用例:
第一行有两个整数N和F,1<=N,F<=10000  分别表示 馅饼的数目和朋友的数目。
第二行有N个整数ri,1<=ri<=10000 表示 馅饼 的半径。
输出
对于每个测试用例,输出一行最大可能的体积V,这样我和我的朋友都可以得到一块体积为V大小的馅饼。
答案V应以浮点数形式给出,绝对误差不超过10^(-3)。

样例
输入复制
3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2
输出复制
25.1327
3.1416
50.2655
说明
题目大意:生日聚会上,来到的所有朋友都会领取一块饼,但是要求的是所有人都要拿到大小相同的饼!
题目要求输出的是:每个人尽量拿到的最大的饼的体积是多大。这里的饼的形状是高为1的圆柱形。V=底面积*高

特别注意:
1、题目里要给你自己留一块。
2、每个人得到的饼不可以是两块饼拼接在一起的。
3、这里的PI:3.141592653589793

标签
二分答案

加油

[此贴子已经被作者于2022-7-22 18:30编辑过]

搜索更多相关主题的帖子: 测试 输出 一行 生日 体积 
2022-07-22 18:17
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:10 
求 ∑( ⌊Ai*Ai*π/x⌋ ) >= n+1 成立的x的最大值

为了简化计算量,可以令 x = y*π,于是上式变为
求 ∑( ⌊Ai*Ai/y⌋ ) >= n+1 成立的y的最大值,x=y*π
2022-07-22 22:27
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:0 
求 ∑( ⌊Ai*Ai/y⌋ ) >= n+1 成立的y的最大值,x=y*π

在  ∑( ⌊Bi/y⌋ ) == m 成立时,怎么求y的最大值?可以这样:
a = Bi/y 求得数量
b = Bi%y 求得剩余
c = b/a 求得对Bi而言,最大的y,设为Ci
最大y = 最小的那个Ci + y

[此贴子已经被作者于2022-7-23 09:54编辑过]

2022-07-23 09:53
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:0 
在  ∑( ⌊Bi/y⌋ ) == m 成立时,怎么求y的最值?可以这样:
a = Bi/y 求得数量
b = Bi/(y+1) 求得最小极限
最小y = 最大的那个Bi

有了求最大最小的方法后,可以随便设一个y,求得m,与n+1比大小,然后确定往上走还是往下走。
或者结合“二分法”,先用二分法确定大体的y值,然后再按上面的方法一步一步地走,这样比单独使用任一方法都要好,完美避开各自的缺点
2022-07-23 11:00
op123
Rank: 6Rank: 6
等 级:贵宾
威 望:21
帖 子:170
专家分:461
注 册:2022-6-4
得分:0 
rjsp已经帮你们梳理好思路了,可以写代码了
2022-07-23 15:27
op123
Rank: 6Rank: 6
等 级:贵宾
威 望:21
帖 子:170
专家分:461
注 册:2022-6-4
得分:0 
算了,结贴吧
2022-07-25 17:31



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-509640-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.309168 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved