二分查找-POJ 3122-Pie

墨蓝 2022-04-18 05:24 187阅读 0赞

## 题目连接：[Pie][] ##

## 题目大意： ##

有N张饼，k个朋友，为了体面，必须把饼切割成大小一样的k+1块（包括主人自己），求出每个人能得到的最大饼体积。

前提：每人一块，饼可以有剩余

二分去暴力答案，确定下界为0，上界为最大体积的饼（每人一块，最大可能就是饼的体积都相等，也就是每块都是最大值）。

## 代码： ##

#include<stdio.h>
    #include<math.h>
    #define MAX_SIZE 100005
    #define max(a,b) (a>b?a:b)
    #define Pi acos(-1.0)    //圆周率
    #define eps 1e-6
    
    double Volume[MAX_SIZE];
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int N,F,ri;
            while(~scanf("%d%d",&N,&F))
            {
                //printf("%lf\n",Pi);
                double Max=-1;
                for(int i=0;i<N;i++)
                {
                    scanf("%d",&ri);
                    Volume[i]=ri*ri*Pi;
                    Max=max(Max,Volume[i]);    //求出最大体积的Pie
                }
    
                double l=0.0,r=Max;
                double Mid;
                while(r-l>eps)
                {
                    Mid=(l+r)/2;
                    int cnt=0;
                    for(int i=0;i<N;i++)
                        cnt+=(int)(Volume[i]/Mid);    //按mid切割（取整）
                    if(cnt>=F+1)    //能分配的人大于F+1，往上取值
                        l=Mid;
                    else
                        r=Mid;
                }
                printf("%.4lf\n",Mid);
            }
        }
        return 0;
    }

[Pie]: http://poj.org/problem?id=3122

发表评论取消回复

表情：

评论列表（有 0 条评论，187人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 2182 Lost Cows 【二分查找+树状数组】

题目大意在一个1-n的排列中告诉你第i个数前面有多少比它小还原这个排列分析从后向前确定如果最后一个数a[n]=i

r囧r小猫/ 2022年10月06日 04:54/ 0 赞/ 190 阅读

相关 HDU 1969 Pie(二分+模拟)

My birthday is coming up and traditionally I'm serving pie. Not just one pie, no, I have

雨点打透心脏的1/2处/ 2022年06月12日 13:09/ 0 赞/ 169 阅读

相关 poj-3122-pie

Pie <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

逃离我推掉我的手/ 2022年05月20日 06:17/ 0 赞/ 162 阅读

相关 Pie————二分+尺取练习

给你n个蛋糕的半径，你有m个朋友，所以总共有m+1个人，现在要分蛋糕，要求每个人分到的大小都是一样的，且每个人的蛋糕都是从一块上切割下来的（不能是2个不同的蛋糕拼起来的），现在

缺乏、安全感/ 2022年05月17日 19:59/ 0 赞/ 180 阅读

相关二分查找-POJ 3122-Pie

题目连接：[Pie][] 题目大意：有N张饼，k个朋友，为了体面，必须把饼切割成大小一样的k+1块（包括主人自己），求出每个人能得到的最大饼体积。前提：每人一

墨蓝/ 2022年04月18日 05:24/ 0 赞/ 188 阅读

相关二分查找

/ 有序数组递归二分查找，定位值的下标 @param arr 目标数组 @param start 起始下标

喜欢ヅ旅行/ 2022年04月06日 14:22/ 0 赞/ 303 阅读

相关查找——二分查找

基本思想二分查找是建立在有序顺序表基础上的！步骤如下： 1. 将表中间位置记录的关键字与给定K值进行比较，若两者相等，则查找成功。 2.

蔚落/ 2022年03月27日 03:46/ 0 赞/ 358 阅读

相关二分查找

二分查找（先排序） typedef struct LNode List; struct LNode{ ElemenType Data[MAXSIZ

爱被打了一巴掌/ 2022年02月02日 17:13/ 0 赞/ 104 阅读

相关二分查找

int search2( int array\[\], int n, int v) \{ int left, right, middle;

心已赠人/ 2021年12月20日 16:07/ 0 赞/ 94 阅读

相关二分查找

二分查找二分查找是一个比较简单的算法，用 C++ 语言实现如下： template <typename T> int binary_search(

ゞ浴缸里的玫瑰/ 2021年12月13日 03:57/ 0 赞/ 162 阅读