Problem C - Pie
Time limit: 1 second
My birthday is coming up and traditionally I'm serving pie. Not justone pie, no, I have a number
N of them, of various tastes andof various sizes. F of my friends are coming to my party andeach of them gets a piece of pie. This should be one piece of one pie,not several small pieces since that looks messy. This piece can be onewhole pie
though.
My friends are very annoying and if one of them gets a bigger piecethan the others, they start complaining. Therefore all of them shouldget equally sized (but not necessarily equally shaped) pieces, even ifthis leads to some pie getting spoiled (which is
better than spoilingthe party). Of course, I want a piece of pie for myself too, and thatpiece should also be of the same size.
What is the largest possible piece size all of us can get? All thepies are cylindrical in shape and they all have the same height 1,but the radii of the pies can be different.
Input
One line with a positive integer: the number of test cases. Thenfor each test case:
- One line with two integers N and F with 1 ≤N, F ≤ 10000: the number of pies and the number offriends.
- One line with N integers ri with 1 ≤ri ≤ 10000: the radii of the pies.
Output
For each test case, output one line with the largest possible volume
V such that me and my friends can all get a pie piece of size
V. The answer should be given as a floating point numberwith an absolute error of at most 10
-3.
Sample Input
3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2
Sample Output
25.1327
3.1416
50.2655
The 2006 ACM Northwestern European Programming Contest
题意:
主人开Party, 厨房有n个派, 邀请了f个小伙伴, 加上自己一共是f+1个小伙伴
然后, 主人分发派, 但是每个人要分到相同大小的派, 且只能是一整块~(一块完完整整的挖掉一小块也算一整块, 但是不许两块及两块以上拼凑)
我们要做的就是求出, 每个人最大能分到多大块的派呢?
做法:
二分法求解!!
一开始的每块大小的边界是: 最小为0, 最大的为 把总面积加起来除以人数(最理想的情况)
然后题目要求误差不超过 10的负三次方~ (这算是二分递归的边界了)
AC代码:
#include<stdio.h>
#include<math.h>
const double PI = acos(-1);
int n, f;
int trueF;
double R[12345];
double search(double l, double r) {
if(r-l < 1e-6)
return l;
double mid = (l + r) / 2.0;
int tSumF = 0; //临时参数, 表示这种情况下饼能分给几个人
for(int i = 0; i < n; i++)
tSumF += R[i] / mid;
if(tSumF >= trueF) //能分更多的人, 表明饼切小了
return search(mid, r);
else //这是切大了
return search(l, mid);
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d %d", &n, &f);
trueF = f + 1; //真正的人数加上自己~
double sumR; //表示总大小
for(int i = 0; i < n; i++) {
scanf("%lf", &R[i]);
R[i] = R[i] * R[i] * PI;
sumR += R[i];
}
printf("%.4lf\n", search(0, sumR/trueF));
}
return 0;
}
分享到:
相关推荐
安国Alcor AU6983量产工具V090409(支持34NM)
sBotClass ... 埃斯基13.08.2014güncellemesindenöncekisürümlerdewp-content / uploads / images dizini olmakzorundadır。 Dikkat(当心!) Tr:下载adverten重新下载edip onuöneçıkarılm
OneKeyTools10-五周年纪念最终版[SP13.08](仅支持PowerPoint) PPT好用工具
型号 额定功率(W) 稳定电压(V) 稳定电流(A) ...12.4~13.08 0.005 RLJZ3.6B O.4 3.55~3.8 0.005 RLJz6.8C 0.4 6.82~7.2 0.005 RLJZ13B 0.4 12.88~13.57 0.005 RLJZ3.
魔法师支票票据打印软件系统用于各类支票打印、进帐单打印、电汇凭证打印、现金交款单打印和业务委托书与业务申请书打印,帮助财务人员减轻日常票据填写工作,并有效避免填写错误。本打印软件是一款具备全自主创建...
学习使用atmega128的Boot Loader功能 实现一个世纪的boot loader程序 程序清单 ...hexbin.exe 13.08 KB main.c 7.31 KB readme.txt 451 bytes TEST.BIN 300 bytes test.hex 860 bytes
改性焦粉吸附亚甲基蓝焓变为43.33 kJ/mol,自由能变在-13.08~-8.46 kJ/mol之间,熵变在0.018~0.041 kJ/mol之间;黏附几率S=5.943×10-9,活化能为41.11 kJ/mol,表明该吸附过程是界面上混乱度增加的自发吸热过程;吸附过程...
全国支票影像交换系统架构介绍:全国支票影像交换系统(影像交换系统)是指综合运用影像技术和支付密码等技术,将纸质支票转化为影像和电子信息,实现纸质支票截留,利用信息网络...实现支票全国通用的业务处理系统。
13.08.2008 AlphaControls v5.62 beta released * Improved design-time editor for the SkinManager.ThirdParty property * Fixed known errors in TsScrollBox, TsTabControl and TsPageControl components * ...
对照组的青春期男孩(平均知识得分为15.35,标准偏差±4.748)在干预后明显高于女性(平均得分为13.08,标准偏差±4.325)(P = 0.009)。 在干预组中,干预后3个月对艾滋病毒/艾滋病有良好知识和良好态度的受访者...
开始安装6点击Finish安装完成,点击Finish7替换破解文件断网,右击桌面快捷方式→属性→打开文件位置,打开软件根目录,将破解补丁复制替换,默认目录:C:\Program Files\ACD Systems\ACDSee Pro\13.08运行注册文件...
结果表明:常温下氧浓度在13.08%时,煤样仍能够发生氧化;风量越小,氧浓度越低,CO气体浓度越高;工作面供风量减小,导致采空区出现CO气体浓度增大,停采时间越长,采空区CO气体浓度越大,但是并不能证明采空区温度有上升趋势...
菲斯金卡德 根据检测文本的等级级别的公式。 见用于检测音节。安装该软件包仅适用于ESM:需要使用Node 12+才能使用它...{ sentence : 1 , word : 13 , syllable : 26 } )// => 13.08原料药该软件包导出以下标识符: fle
结果表明:无论5月和9月,随着生长光强的降低,苦槠幼苗叶片的最大净光合速率、光补偿点和光饱和点均有减小的趋势,尤其在9月,在15%自然光强下分别为13.08Vmol・m-2・s-1,962umolm-Zs-1,198.80协mol・m-2・s-1,显著...
为探讨He-Ne激光对紫外线-B(UV-B)辐射损伤修复途径,采用He-Ne激光辐照(5 mW·mm-2)进行照射,对增强UV-B(13.08 kJ·m-2·d-1)辐射下水稻幼苗的叶绿素含量、核酮糖-1,5-二磷酸羧化酶/加氧酶(rubisco)亚基含量及反映...