poj3122

时间:2022-04-25 07:32:30

题目大意:馅饼(看起来像是一个简单点的题目啊,嘎嘎,希望是的吧)

我的生日即将来临按照习惯我将准备馅饼,不是一个馅饼,我有N块馅饼,有各种各样的味道和尺寸,当我的朋友来参加我的聚会平且他们都能得到一块馅饼,这应该是一块馅饼,不是几小块看起来很乱的样子,这些馅饼曾经是一个完整的个体。
我的朋友十分的讨厌别人拿的馅饼比自己的大,他们开始抱怨,因此他们都应该得到大小相同的尺寸(但是不一定形状相同)馅饼,即使这样导致一些馅饼变质(总比破话聚会好吧),当然我自己也想要一块馅饼,并且尺寸相同。
我们能获得的最大尺寸的馅饼是多少?所有的馅饼都是圆柱型并且有相同的高度1,但是馅饼的半径是不同的
明白了,就是说这个人有很多个馅饼,他和他的朋友吃的馅饼大小都是一样的,问他们最多吃的馅饼的体积是多少
分析:仔细想了一会感觉还是二分面积好点,希望复杂度可以承受

确实是可行的方案

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; #define maxn 10005
#define PI 3.14159265358979323846//精度必须高,否则无情WA
#define esp 1e-5 double area[maxn]; bool cmp(double n1, double n2)
{
    return n1 > n2;
}
int Slove(int N, int M, double S)
{
    int i, sum=0;     for(i=0; i<N; i++)
    {
        sum += (int)(area[i]/S);         if(sum >= M)return 1;
    }     return 0;
} int main()
{
    int T;     scanf("%d", &T);     while(T--)
    {
        int i, N, M, r;         scanf("%d%d", &N, &M);
        M++;         for(i=0; i<N; i++)
        {
            scanf("%d", &r);
            area[i] = PI * r * r;
        }         sort(area, area+N, cmp);         double L=0, R=area[0], Mid;         while(R-L>esp)
        {
            Mid = (R+L) / 2;             int ans = Slove(N, M, Mid);             if(ans)
                L = Mid + esp;
            else
                R = Mid - esp;
        }         printf("%.4f\n", Mid);
    }     return 0;
} /*
25 5 5
2
14
11
21
17 3 2 0
1
2
a
*/