uva 10385 - Duathlon(三分)

本文主要是介绍uva 10385 - Duathlon(三分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：uva 10385 - Duathlon

题目大意：n个人参加铁人二项，跑步和自行车，给定总长度，以及n个人的速度。然后第n个人贿赂了举办者，所以举办者会尽量调整两个项目的长度比例，然后第n个人获胜，问第n个人可以先第二名多久。

解题思路：列出n-1个一元方程，对应成单峰函数，所以用三分求解即可。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 30;int N;
double L, vr[maxn], vk[maxn];void init () {for (int i = 1; i <= N; i++) {vr[i] = 1/vr[i] - 1/vk[i];vk[i] = L/vk[i];}for (int i = 1; i < N; i++) {vr[i] -= vr[N];vk[i] -= vk[N];}
}double f (double x) {double ret = vr[1] * x + vk[1];for (int i = 2; i < N; i++)ret = min(ret, vr[i] * x + vk[i]);return ret;
}double tsearch (double l, double r) {for (int i = 0; i < 100; i++) {double p = l + (r - l) / 3;double q = r - (r - l) / 3;if (f(p) > f(q))r = q;elsel = p;}return l;
}int main () {while (scanf("%lf%d", &L, &N) == 2) {for (int i = 1; i <= N; i++)scanf("%lf%lf", &vr[i], &vk[i]);init();double x = tsearch(0, L);if (f(x) < 0)printf("The cheater cannot win.\n");elseprintf("The cheater can win by %.0lf seconds with r = %.2lfkm and k = %.2lfkm.\n", f(x) * 3600, x, L-x);}return 0;
}

这篇关于uva 10385 - Duathlon(三分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---