学步园

很明显的二分搜索，注意一下精度就OK了

我所知道的二分有俩种写法，注意一下循环的控制

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
double cal(double x)
{
return 8*x*x*x*x+7*x*x*x+2*x*x+3*x+6;
}
int main()
{
double y;
int T;
    scanf("%d",&T);
while(T--)
    {
        scanf("%lf",&y);
if(y<cal(0) || y>cal(100))
        {
            printf("No solution!\n");
continue;
        }
double left=0,right=100;
while(left<right)
        {
double mid=(left+right)/2.0;
double temp=cal(mid);
if(fabs(temp-y)<=1e-6)
            {
                printf("%.4f\n",mid);
break;
            }
else if(temp>y)
                right=mid;
else left=mid;
        }
    }
return 0;
}

#include <iostream>
#include <math.h>
using namespace std;
double y = 0;
double cal(double x)
{
return 8*x*x*x*x+7*x*x*x+2*x*x+3*x+6;
}
int main ()
{
int T;
    scanf ( "%d",&T );
while ( T -- )
    {
          scanf ( "%lf",&y );
if ( cal(0) > y || cal(100) < y )
          {
               printf ( "No solution!\n" );
continue;
          }
double left = 0.0, right = 100.0;
while ( right - left > 1e-6 )
          {
double mid = ( left + right ) / 2.0;
double temp = cal ( mid );
if ( temp > y )
                     right = mid - 1e-6;    
else 
                     left = mid + 1e-6;
          }
          printf ( "%.4lf\n",( left + right ) / 2.0 ); 
    }
return 0; 
}

hdu2899 跟上面类似的题目，只是先求一下导就OK了

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
double y;
double cal(double x)
{
return 42*pow(x,6) +48*pow(x,5) +21*x*x+10*x;
}
double Fx(double x)
{
return 6 * pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*x*x-y*x;
}
int main()
{
int T;
    scanf("%d",&T);
while(T--)
    {
        scanf("%lf",&y);
double left=0,right=100,temp;
while(left<right)
        {
double mid=(left+right)/2.0;
            temp=cal(mid);
if(fabs(temp-y)<=1e-5)
            {
                printf("%.4f\n",Fx(mid));
break;
            }
else if(temp<y)
                left=mid;
else right=mid;
        }
    }
return 0;
}

 hdu1551 Cable master

题意：已知有多少根电缆，以及想要切成的相等的电缆的数目，求切成的电缆的最大长度

若求得的电缆的长度小于0.01 ，则输出0.0

分析：二分切成的电缆的长度逼近即可

#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int n,k;
double a[10001],maxlen;
int cal(double c)
{
int t=0;
for(int i=0;i<n;i++)
        t+=(int)(a[i]/c);
return t;
}
int main()
{
while(scanf("%d %d",&n,&k)==2 && (n||k))
    {
        maxlen=0.0;
for(int i=0;i<n;i++)
        {
            scanf("%lf",&a[i]);
            maxlen=max(maxlen,a[i]);
        }
double left=0.01,right=maxlen,mid;
while(right-left>1e-5)
        {
            mid=(left+right)/2;
int t=cal(mid);
if(t>=k)
                left=mid;
else right=mid;
        }
int t=cal(left);
if(t>=k)
            printf("%.2f\n",left);
else printf("0.0\n");
    }
return 0;
}