HDU 2241 考研路茫茫——早起看书

题目链接~~>

做题感悟：理解错题意了，我以为图象只有两段，所以我分了两段分别三分，两组样例只对了一个，看了别人的才知道需要对每一段三分。

解题思路：根据题意：可以将图象分成 m - 1 段 a0 ~ a1 , a1 ~ a2 , ai ~ ai+1 , an-2 ~ an-1  对每段三分即可，为什么要这样呢？

               假设 ： 最小值为 F( x ) , so  F( x ) = n / (x * x ) + k * x + b ;这个函数在某段区间可能是单调递增的，也可能先递减后递增，这样都没关系三分都可以解决，如果单纯的用二分先递减再递增的情况就解决不了。

代码：

  

   

    

     

    
    

     

      #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 double INF = 999999999 ;
     
    
   

    

     

    
    

     

      const double esp = 1e-8 ;// 精确到 7 位即可
     
    
   

    

     

    
    

     

      const lld  md= 2810778 ;
     
    
   

    

     

    
    

     

      const int MX = 10005 ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 double x,y ;
     
    
   

    

     

    
    

     

      }T[MX] ;
     
    
   

    

     

    
    

     

      int n ;
     
    
   

    

     

    
    

     

      double m,k,b,mx ;
     
    
   

    

     

    
    

     

      double find(double x)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return m/(x*x)+k*x+b ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      double third_search(double le,double rt)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 double m1,m2,mid,midd ;
     
    
   

    

     

    
    

     
 while(le+esp<=rt)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       mid=(rt+le)/2.0 ;
     
    
   

    

     

    
    

     

       midd=(mid+rt)/2.0 ;
     
    
   

    

     

    
    

     

       m1=find(mid) ;
     
    
   

    

     

    
    

     

       m2=find(midd) ;
     
    
   

    

     

    
    

     

       m1 > m2 ? le=mid : rt=midd ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return find(mid) ;// 切记不要把 mid 换成 le
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 while(~scanf("%d%lf",&n,&m))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     
 scanf("%lf%lf",&T[i].x,&T[i].y) ;
     
    
   

    

     

    
    

     
 double best=INF ;
     
    
   

    

     

    
    

     
 for(int i=1 ;i<n ;i++) // 对每一段三分
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       k=(T[i].y-T[i-1].y)/(T[i].x-T[i-1].x) ;
     
    
   

    

     

    
    

     

       b=T[i].y-k*T[i].x ;
     
    
   

    

     

    
    

     

       mx=third_search(T[i-1].x,T[i].x) ;
     
    
   

    

     

    
    

     
 if(mx<best)
     
    
   

    

     

    
    

     

       best=mx ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%.3lf\n",best) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/23118039