【三分】HDU 2241 考研路茫茫——早起看书_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 【三分】HDU 2241 考研路茫茫——早起看书

【三分】HDU 2241 考研路茫茫——早起看书

 2011/12/13 9:18:16  基德KID.1412  http://972169909-qq-com.iteye.com  我要评论(0)
  • 摘要: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<jXi<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
  • 标签:
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 10005
const 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;
}
  • 大小: 12.7 KB
  • 大小: 8.1 KB
  • 大小: 166.7 KB
  • 查看图片附件
  • 相关文章
发表评论
用户名: 匿名