【三分】HDU 2241 考研路茫茫——早起看书
KIDx 的解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2241
第4名
解题思路：
由题意得：【设题目所给m个点存放到点结构p[m]中】
F = n/(x^2)
设Y是第i-1个点跟第i个点连线的方程【设k是这2点连线的斜率】
则：【根据题目：i<j Xi<Xj 且 Yi<=Yj】
Y = k * (x-p[i-1].x) + p[i-1].y
设总的函数 = Z
则Z = Y + F = n/(x^2) + k * (x-p[i-1].x) + p[i-1].y
即：Z = n/(x^2) + k*x + (p[i-1].y - k*p[i-1].x)
由于点已经给出，所以绿色部分为常数部分，不会影响函数单调性
∴可以提出来，不用放到代码中Z函数内，因为三分里要运行很多次Z函数，这样无意中就增加了运行时间
如图：
简单联想可知对于第k段来说，Z函数有可能是单调的，也有可能是先减后增的函数，但是对于(0,+无穷)来说，Z函数可能有多个极值，所以必须分段【可以从分段函数的角度理解】进行三分求最小值
#include <iostream>using namespace std;#define eps 1e-4#define M 10005const double inf = 1e100; //定义无穷大int n, m;struct point{ int x, y;}p[M];double Z (double x, double k) {return n/(x*x) + k*x;}int main(){ int i; double l, r, mid1, mid2, mins, tp1, tp2; while (~scanf ("%d%d", &m, &n)) { for (i = 0; i < m; i++)scanf ("%d%d", &p[i].x, &p[i].y); mins = inf; for (i = 1; i < m; i++) //分段求解 { l = p[i-1].x, r = p[i].x;double k = (p[i].y - p[i-1].y + 0.0) / (p[i].x - p[i-1].x); //求斜率 while (r - l > eps) //三分逼近函数极值 { mid1 = l + (r-l)/3; mid2 = r - (r-l)/3; tp1 = Z (mid1, k); tp2 = Z (mid2, k); if (tp1 > tp2) l = mid1; else r = mid2; }tp1 += p[i-1].y - k*p[i-1].x; //把常数加上 if (mins > tp1) mins = tp1; //更新最小值 } printf ("%.3f\n", mins); } return 0;}