首页 > 代码库 > LA 3635 派
LA 3635 派
题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1636
题意：
f+1个人，来分 n 个圆形派，每个人只能从一个派中拿，也就是说，不能从两个里面去拼。
求每个人最大的面积。
分析：
二分。
二分能够得到的最大面积x，怎么判断是否可以分到呢？ 把每一个派分成 x，有多少份>=f+1,即可；
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = 10000 + 5; 6 const double PI = acos(-1.0); 7 8 int n,f; 9 double A[maxn];10 11 bool ok(double x) {12 int sum = 0;13 for(int i=0;i<n;i++) {14 sum +=(A[i]/x);15 }16 if(sum>=f+1)17 return true;18 return false;19 }20 21 int main()22 {23 int t;24 scanf("%d",&t);25 while(t--) {26 scanf("%d%d",&n,&f);27 double l=0;28 double r=-1;29 for(int i=0;i<n;i++) {30 int x;31 scanf("%d",&x);32 A[i] = PI*x*x;33 r=max(r,A[i]);34 }35 36 while(r-l>1e-5) {37 double M = (l+r)/2;38 if(ok(M)) l = M;39 else r = M;40 }41 printf("%.4lf\n",l);42 }43 return 0;44 }
LA 3635 派
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。