LA 3635

本文主要是介绍LA 3635，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题干：

大意是f+1个人来分n个圆形派（每个的大小不一定相同）。每个人必须分得一整块，而且每个人分得的面积相同。求每个人分得的最大面积是多少。

分析：

看了看书上的分析，就是采用二分法，查找到合适的面积x，使得问题转化为“能否可以让每人得到一块x的派”。

代码：

#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
const int maxn = 10010;
double num[maxn];
int n,f;
const double PI = acos(-1.0);bool ok(double m)//判断是否满足面积为x的时候，有足够的派分给f+1个人
{int sum = 0;for(int i = 0;i < n;i++){sum += floor(num[i] / m);}return sum >= (f + 1);
}int main()
{int T;cin>>T;while(T--){memset(num,0,sizeof(num));scanf("%d%d",&n,&f);int x;double maxa = -1;for(int i = 0;i < n;i++){cin >> x;num[i] = PI * x * x;maxa = max(maxa,num[i]);}double mina = 0;while(maxa - mina > 1e-5){double M = (maxa + mina) / 2;if(ok(M))mina = M;elsemaxa = M;}printf("%.4lf\n",mina);}return 0;
}

这篇关于LA 3635的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---