分派pie（二分法）

2．问题描述

我的生日要到了！根据习俗，我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对，每个人会拿到一块派（必须一个派的一块，不能由几个派的小块拼成；可以是一整个派）。

我的朋友们都特别小气，如果有人拿到更大的一块，就会开始抱怨。因此所有人拿到的派是同样大小的（但不需要是同样形状的），虽然这样有些派会被浪费，但总比搞砸整个派对好。当然，我也要给自己留一块，而这一块也要和其他人的同样大小。

请问我们每个人拿到的派最大是多少？每个派都是一个高为1，半径不等的圆柱体。

输入

第一行包含两个正整数N和F，1 ≤ N, F ≤ 10 000，表示派的数量和朋友的数量。

第二行包含N个1到10000之间的整数，表示每个派的半径。

输出

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

输入样例

3 3

4 3 3

输出样例

25.133

二分法————分pie

思路如下

题意：给你 n 个pie，m + 1 个人，每个pie的高度相同，只是他们的半径不同，

然而这个m + 1个人还很挑剔，被分的每块子 pie 必须只能来自 n块 pie中的其中一块

思路：这一题就是简单的二分，我先假设分给每个人的子pie 为 mid ，再通过二分不断缩减精确这个，所分子pie的假设值，，，，，，，在这样我就可以得到我们想要的值

这一题的思路还可以参照与该题相似的题

题解如下

#include<iostream>

#include<cmath>

using namespace std;

const double pi = acos(-1);    //求圆周率

const int Len = 10005;

const double cha = 0.00001;		//⚠️精读尽量开大一点，防止出错

int n,m;

int ar[Len];

double ans;					  //每个人所能分的最大子pie的大小

bool judge(double mid)

{

    int m_cnt = m;            //总共需要分割的数量

    for(int i = 1; i <= n; i ++)

    {

        double V = pi * ar[i] * ar[i];

        if(V >= mid)

        {

            m_cnt -= int(V / mid);

        }

        if(m_cnt <= 0)

        {

            return true;

        }

    }

    return false;

}

void Binary_search(double l ,double r)

{

    while(r - l > cha)

    {

        double mid = (l + r) / 2;

        if(judge(mid))           //如果我这个假设的 子pie的大小mid，是可以完全由 n 张 pie 分割出来，那么我们要考虑 能不能把 假设子pie大小mid 调大一些（通过调整下限 mn = mid），这样再进行尝试

        {

            ans = mid;

            l = mid;

        }

        else           //不能够分割出来m块大小为 mid的子pie，那么我们就缩小，mid值（通过调整 上线mx = mid）

        {

            r = mid;

        }

    }

    printf("%.3lf\n",ans);

}

int main()

{

    //freopen("T.txt","r",stdin);

    scanf("%d %d", &n, &m);

    m ++;       //包括自己，所以总人数 + 1

    for(int i = 1; i <= n; i ++)

        scanf("%d",&ar[i]);

    Binary_search(0 , pi * Len * Len);

    return 0;

}

巴特西

分派pie（二分法）

思路如下

题解如下

最新文章

热门文章