• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ3122 – Pie

    ACM-POJ EXP 104阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    就是公平地分披萨pie

    我生日,买了n个pie,找来f个朋友,那么总人数共f+1人

    每个pie都是高为1的圆柱体,输入这n个pie的每一个尺寸(半径),如果要公平地把pie分给每一个人(就是所有人得到的pie尺寸一致,但是形状可以不同),而且每个人得到的那份pie必须是从同一个pie上得到的

    后面那句很重要,

    就是说如果有3个pie, 尺寸分别为1,2,3,

    如果要给每人尺寸为2的pie,那么最多分给2个人,而不是3个人

    因为第一个pie尺寸为1,小于2,扔掉

    第二个pie尺寸为2,等于2,刚好分给一个人

    第三个pie尺寸为3,切出尺寸为2的一份,分给一个人,剩下的尺寸为1的就扔掉

    千万不要陷入 (1+2+3)/2=3人的误区,这样就变成求平均了

    解题思路

    非常水的二分题,千万要注意,输入的是朋友的数量f,分pie是分给所有人,包括自己在内共f+1人

    下界low=0,即每人都分不到pie

    上界high=maxsize,每人都得到整个pie,而且那个pie为所有pie中最大的 (上界就是 n个人n个pie,每个pie还等大)

    对当前上下界折中为mid,计算”如果按照mid的尺寸分pie,能分给多少人

    求某个pie(尺寸为size)按照mid的尺寸,能够分给的人数,就直接size / mid,舍弃小数就可以

    由于每个pie都是圆的,为了保证精度和减少运算,我的程序在计算过程中把 π 先忽略,仅仅用半径R²去计算,最后的结果再乘π


    没难度的二分题,若果WA要多多留意是不是精度问题,因为算法思路是很明确的,精度才是最头疼的

    转载请注明:EXP 技术分享博客 » POJ3122 – Pie

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址