【三分搜索算法】UVa 10385 - Duathlon

浏览数：48 / 时间：2015年06月08日

题意：“铁人三项”比赛中，需要选手在t km的路程里进行马拉松和骑自行车项目。现有n名选手，每位选手具有不同的跑步速度和骑车速度。其中第n位选手贿赂了裁判员,裁判员保证第n名选手一定会取得冠军。问当马拉松路程与自行车路程分别为多少时，第n名选手才能取得冠军。

输出冠军与第二名所差的秒数以及马拉松路程与自行车路程。

分析：

设马拉松路程为r时选手i的用时：f(r) = r/rv[i] + (t-r)/kv[i] = ((kv[i]-rv[i])*r + t*rv[i])/(kv[i]*rv[i]);

由于kv[i]-rv[i]正负未知，则f(r)可以看做是一单峰极值曲线。选用三分法求解；

三分法求解思路：

技术分享

上图中，蓝色线代表第n位选手在r取(0，t)时的用时，橙色线代表其他n-1名选手的最短用时，红线为橙线减蓝线的差值（注意此时红线的值为负）。可知，要使第n名选手获胜，必须取蓝线低于橙线的r值。

以橙线值(tmp)减蓝线值(min_)的差(error，红线)为判断依据，error为正，表示第n名选手用时最短，此时取得r值。那么问题就简化为求error值的最大值。

取三分点m1,m2,若m1的error值大于m2的error值，那么答案就在[L, m2]范围内；否则在[m1, R]范围内。

代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 using namespace std;
 5 const int maxn = 30;
 6 int t, n;
 7 double rv[maxn], kv[maxn];
 8 double Judge (double r)
 9 {
10     double min_ = r/rv[n-1]+(t-r)/kv[n-1];
11     double error = 1e100; //
12     for(int i = 0; i < n-1; i++)
13     {
14         double tmp = r/rv[i]+(t-r)/kv[i];
15         error = min(error, tmp-min_);
16     }
17     return error;
18 }
19 
20 int main()
21 {
22     while(~scanf("%d", &t))
23     {
24         scanf("%d", &n);
25 
26         for(int i = 0; i < n; i++)
27         {
28             scanf("%lf%lf", &rv[i], &kv[i]);
29         }
30         double L = 0.0, R = t;
31 
32         bool ok = false;
33         while(R-L>1e-7)
34         {
35             double m1 = L + (R-L)/3;
36             double m2 = R - (R-L)/3;
37             //cout << Judge(m1) << " " << Judge(m2) << endl;
38             if(Judge(m1) > Judge(m2)) R = m2;
39             else L = m1;
40         }
41         double err = Judge(L);
42         if(err < 0.00)
43             printf("The cheater cannot win.\n");
44         else
45             printf("The cheater can win by %.0lf seconds with r = %.2lfkm and k = %.2lfkm.\n", err*3600, L, t-L);
46     }
47     return 0;
48 }