UVA 10385 - Duathlon
题意：一些运动员，參加铁人两项，跑步r千米，骑车k千米，如今知道每一个人的跑步和骑车速度，问是否能设置一个r和k，保持r + k = t，使得第n个人会取胜，假设能够求出时间和r，k
思路：三分法，把每一个人列出一个带r的方程求时间，其它人减去最后一个人就是相差的时间，发现这些方程都是一元一次线性方程，而问题相当于求每一个x轴上，值最小的那个，这些线画出来，会发现变成一个上凸函数，是单峰函数，能够用三分法求解
代码：
#include#include #include 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;}