做题感悟:刚开始做时完全没有思路,甚至题意都不怎么清楚,但是当下定决心解决它时就很容易解决了。
解题思路:二分:算出最小份蛋糕的体积和最大份蛋糕的体积,然后枚举每一种情况看是否满足(让esp = 1e - 7 即可,精确到 8 会超时)。
代码:
#include<stdio.h> #include<iostream> #include<map> #include<stack> #include<string> #include<string.h> #include<stdlib.h> #include<math.h> #include<vector> #include<queue> #include<algorithm> using namespace std ; #define LEN sizeof(struct node) #define pret(a,b) memset(a,b,sizeof(a)) #define lld __int64 const double PI = 3.1415926535898 ; const int INF = 99999999 ; const double esp = 1e-7 ;// 精确到 7 位即可,8位超时 const long long mod= 1000 ; const int MX = 10005 ; int n,m ; double a[MX] ; bool find(double x) { int ans=0 ; for(int i=n-1 ;i>=0 ;i--) { ans=ans+(int)(a[i]/x) ; if(ans>=m) return true ; } return false ; } double binary_search(double le,double rt) { double mid ; mid=(le+rt)/2.0 ; // 如果le == rt 的情况 while(le+esp<=rt) { mid=(rt+le)/2.0 ; find(mid) ? le=mid : rt=mid ; } return mid ; } int main() { int Tx ; scanf("%d",&Tx) ; while(Tx--) { scanf("%d%d",&n,&m) ; m++ ; double x,sum=0 ; for(int i=0 ;i<n ;i++) { scanf("%lf",&x) ; a[i]=PI*x*x ; sum+=a[i] ; } sort(a,a+n) ; double le=a[n-1]/m,rt=sum/m ; printf("%.4lf\n",binary_search(le,rt)) ; } return 0 ; }