UVA 10385 - Duathlon(三分法)

UVA 10385 - Duathlon

题目链接

题意：一些运动员，參加铁人两项，跑步r千米，骑车k千米，如今知道每一个人的跑步和骑车速度，问是否能设置一个r和k，保持r + k = t，使得第n个人会取胜，假设能够求出时间和r，k

思路：三分法，把每一个人列出一个带r的方程求时间，其它人减去最后一个人就是相差的时间，发现这些方程都是一元一次线性方程，而问题相当于求每一个x轴上，值最小的那个，这些线画出来，会发现变成一个上凸函数，是单峰函数，能够用三分法求解

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 25;

double t, v1[N], v2[N];

int n;

double cal(double r) {

    double k = t - r;

    double ans = 1e100;

    double t1 = r / v1[n - 1] + k / v2[n - 1];

    for (int i = 0; i < n - 1; i++) {

	double t2 = r / v1[i] + k / v2[i];

	ans = min(ans, t2 - t1);

    }

    return ans;

}

int main() {

    while (~scanf("%lf", &t)) {

	scanf("%d", &n);

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

	    scanf("%lf%lf", &v1[i], &v2[i]);

	double l = 0, r = t;

	for (int i = 0; i < 100; i++) {

	    double midl = (l * 2 + r) / 3;

	    double midr = (l + r * 2) / 3;

	    if (cal(midl) > cal(midr)) r = midr;

	    else l = midl;

	}

	double ti = cal(l);

	if (cal(l) < 0.00) printf("The cheater cannot win.\n");

	else printf("The cheater can win by %.0lf seconds with r = %.2lfkm and k = %.2lfkm.\n", ti * 3600, l, t - l);

    }

    return 0;

}