本文主要是介绍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 ;
}
这篇关于HDU 2241 考研路茫茫——早起看书的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
