题解 P5485 【[JLOI2010]铁人双项比赛】

_•́へ•́╬_ · 2020-01-22 22:29:36 · 题解

思路

首先，大家一定能想到：做出k，然后s-k就是 r

对于本题，一定能找到一个k，使他领先第二名最多。比k大一点都不行，比k小一点也不行。所以用三分

代码

#include<stdio.h>
int s,n;double a[100],b[100],l,r,m1,m2;
inline void min(double&x,const double&y){if(x>y)x=y;}//min
inline double cal(const double&k,const double&r)//计算
{
    register double minn=1e9;
    for(register int i=0;i<n-1;++i)min(minn,k/a[i]+r/b[i]);
    return minn-(k/a[n-1]+r/b[n-1]);
}
main()
{
    scanf("%d%d",&s,&n);
    for(register int i=0;i<n;++i)scanf("%lf%lf",a+i,b+i);//输入
    for(l=0,r=s;r-l>1e-8;)//三分
    {
        m1=l+(r-l)/3;m2=r-(r-l)/3;
        if(cal(m1,s-m1)>=cal(m2,s-m2))r=m2;//m1比m2更优
        else l=m1;//m2更优
    }
    if(cal(l,s-l)<0)puts("NO");//他必输
    else printf("%.2lf %.2lf %.0lf",l,s-l,cal(l,s-l)*3600);//输出
}