NC20126. [JLOI2010]铁人双项比赛
描述
输入描述
你的程序从文件读入输入数据。
输入的第一行是两个正整s和n，s表示总赛程（单位为公里，s ≤ 231），n表示参赛总人数（2 ≤ n ≤ 100）。
接下来的n行每行是两个实数，分别表示每个选手长跑的平均速度和骑车的平均速度（单位为千米/小时）。
第n个选手就是指定的选手，你的任务是求出对他最有利的k和r。
输出描述
你的程序的输出包括三个数k，r, t，分别表示对第n号选手最有利的k和r（浮点数，保留小数点后2位），以及在选择k和r的情况下，第n号选手最多可以领先第2名多少秒（四舍五入到整数）；如果另一个选手和该选手并列第一，则ti=0。倘若无论选择什么k，r都不能使第n号选手获胜，则输出“NO”。
示例1
输入:
100 3 10.0 40.0 20.0 30.0 15.0 35.0
输出:
14.29 85.71 612
C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 504K, 提交时间: 2020-03-22 23:25:28
#include<cstdio>
int n;
double s;
double v1,v2;
double a[105],b[105];
double km=0,ans=-1.0e50;
void cal(double x)
{
if(x<0||x>s) return;
double y=1.0e50,c;
for(int i=1;i<n;i++)
{
c=a[i]*x+b[i];
if(c<y) y=c;
}
y-=a[n]*x+b[n];
if(y>ans) ans=y,km=x;
}
int main()
{
scanf("%lf%d",&s,&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&v1,&v2);
a[i]=1.0/v1-1.0/v2;
b[i]=s/v2;
}
for(int i=1;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
cal((b[j]-b[i])/(a[i]-a[j]));
}
}
cal(0);
cal(s);
if(ans>=0) printf("%.2lf %.2lf %.0lf",km,s-km,ans*3600.0);
else puts("NO");
return 0;
}