分蛋糕问题 要求每一块蛋糕体积相等 其实就是求r[i]能分解为f+1个相同的数的最大值 二分水过
#include<iostream> #include<cstdlib> #include<cstdio> #include<string> #include<vector> #include<deque> #include<queue> #include<algorithm> #include<set> #include<map> #include<stack> #include<ctime> #include<cmath> #include<list> #include<cstring> //#include<memory.h> using namespace std; #define ll long long #define ull unsigned long long #define pii pair<int,int> #define INF 1000000007 #define pll pair<ll,ll> #define pid pair<int,double> #define sci(a) scanf("%d",&a) #define scd(a) scanf("%lf",&a) #define scs(a) scanf("%s",a) #define pri(a) printf("%d\n",a); #define prd4(a) printf("%.4lf\n",a); #define prs(a) printf("%s\n",a); const double eps=1e-6; #define N 10005 int r[N];//半径 const double PI=4.0*atan(1.0); bool check(double size,int n,int f){//能否分出f个size大小的蛋糕 int sum=0; for(int i=0;i<n;++i){ sum+=(int)(r[i]/size);//这里好奇怪 如果加上eps居然WA if(sum>=f) return true; if(r[i]<=size+eps) return false; } return false; } double Bin_Search(int n,int f){//二分找最大size double MAX=r[0],MIN=0,mid,res=0; while(MAX-MIN>eps){ mid=(MIN+MAX)/2; if(check(mid,n,f)){ MIN=mid; res=mid; } else MAX=mid; } return res; } int main(){ //freopen("/home/lu/文档/r.txt","r",stdin); //freopen("/home/lu/文档/w.txt","w",stdout); int t,n,f; sci(t); while(t--){ sci(n); sci(f); ++f; for(int i=0;i<n;++i){ sci(r[i]); r[i]*=r[i]; } sort(r,r+n,greater<int>()); prd4(Bin_Search(n,f)*PI) } return 0; }