更新时间:2022-08-12 16:31:05
思路:二分
分析:
1 题目说的是有n块圆形的饼,饼的高度都是1但是半径不一定相同。现在有f+1个人(算上自己),想要平均分得一块面积相同的饼,必须是一块不能够是组合起来的,问这f+1个人能够分到的最大的面积是多少
2 很明显的二分ans,然后对n块饼进行判断,利用二分逼近的思想求出ans
3 注意这样一题的精度要求很高,pi = 3.1415926535898,还有eps不能取太小会TLE。
代码:
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define MAXN 10010 #define pi 3.1415926535898 #define eps 1e-6 int t , N , F; double sum; double r[MAXN]; void solve(){ double left , right , mid; left = 0; right = 1.0*(pi*sum)/F; while(right-left > eps){ mid = left+(right-left)/2.0; int count = 0; for(int i = 0 ; i < N ; i++){ double s = pi*r[i]*r[i]; int tmp = s/mid; count += tmp; } if(count < F) right = mid; else left = mid; } printf("%0.4lf\n" , right); } int main(){ scanf("%d" , &t); while(t--){ scanf("%d%d" , &N , &F); sum = 0; F++; for(int i = 0 ; i < N ; i++){ scanf("%lf" , &r[i]); sum += r[i]*r[i]; } solve(); } return 0; }
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const double eps = 1e-6; const double PI = 3.1415926535898; const int MAXN = 10010; int n , numFriend; struct pie{ double r; double size; }; pie p[MAXN]; bool judge(double s){ int cnt = 0; for(int i = 0 ; i < n ; i++) cnt += p[i].size/s; return cnt >= numFriend+1 ? true : false; } double solve(double Min , double Max){ double left , right , mid; left = Min , right = Max; while(right-left > eps){ double mid = left+(right-left)/2; if(judge(mid)) left = mid; else right = mid; } return left; } int main(){ int Case , pos; double Min , Max; scanf("%d" , &Case); while(Case--){ scanf("%d%d" , &n , &numFriend); Max = 0.0 , Min = 1>>30; for(int i = 0 ; i < n ; i++){ scanf("%lf" , &p[i].r); p[i].size = PI*p[i].r*p[i].r; Max = max(Max , p[i].size); Min = min(Min , p[i].size); } printf("%.4lf\n" , solve(Min , Max)); } return 0; }