HDUOJ PIE二分查找

it2024-11-07  10

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>#include <vector>#include <stack>#include <queue>#include<cassert>#include<set>using namespace std ;#ifdef DeBUG#define bug assert#else#define bug //#endif#define eps 1e-6  int m,n;  double pie[11000];bool test(double x)//判断是否每个都分成出x体积大的蛋糕的块数>=人数,=人数那最好了^_^{ int sum=0; for(int i=0;i<m;i++) sum+=(int)(pie[i]/x); if(sum>=(n+1)) return true; else return false;}int main(){ #ifdef DeBUG  freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin); #endif int T; const double PI=acos(-1.0); scanf("%d",&T); while(T--) {  int i,j,k;  int r;  double maxx=0.0;  scanf("%d%d",&m,&n);  for(i=0;i<m;i++)  {   scanf("%d",&r);   pie[i]=(r*r*PI);   maxx+=pie[i];  }  double low=0.0,high=maxx/(n+1),mid;  while(high-low>eps)  {   mid=(high+low)/2;   if(test(mid))   low=mid;   else   high=mid;  }  printf("%.4lf\n",mid); }  return 0;}

还有个代码就都贴上吧

#include<iostream>#include<cstdio>#include<cmath>

using namespace std;const double eps=1e-6;const double PI=acos(-1.0);int p[10000];

int main(){//freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin);    int t,n,m,cnt;    double low,mid,up;    cin>>t;    while(t--)    {        cin>>n>>m;        m++;        low=up=0;        for(int i=0;i<n;i++)        {            scanf("%d",p+i);            p[i]*=p[i];            if(up<p[i])                up=p[i];        }        while(up-low>=eps)        {            mid=(low+up)/2;            cnt=0;            for(int i=0;i<n;i++)                cnt+=(int)(p[i]/mid);            if(cnt<m)                up=mid-eps;            else if(cnt>=m)//此处很重要                low=mid+eps;        }        printf("%.4lf\n",mid*PI);    }    return 0;}

转载于:https://www.cnblogs.com/Skyxj/p/3183996.html

最新回复(0)