题解 P3218 【[HNOI2011]赛车游戏】

· · 题解

这道题乍一看挺复杂的,其实思路理清之后还是比较简单的吧。

首先我们可以手玩几组数据,发现取到最优解总是在每一段的速度都比较平均的情况下取到,因此我们不妨大胆猜想：
最优解在速度基本相同的情况下最优。

大概的证明如下(转自http://blog.163.com/bill125_zjh/blog/static/231801006201441025744282/):

反正我是看不懂QwQ,但是我们学的是OI不是数学,所以我们只要有猜想就好了对吧(雾

好的那么有了这两个个性质后,我们再继续观察题目中的耗油量的表达式:

a*v+b*s

其中a,b,s 都是定值,那么这个表达式我们就可以看做 k*x+b 的形式,即耗油量与速度成正比。

结合以上,我们可以二分整段速度的最大值,再由这个速度计算出最优解就好了。

计算这里还有一个细节,若 a*v+b*s \le 0,由题意这个时候的耗油量一定是0。
但这个时候显然速度是可以更大的,

由 a*v+b*s=0

v=-\frac{b*s}{a}

这个时候 min\{-\frac{b*s}{a},maxv\} 才是更优的速度。

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-15;
const int N=10010;
struct Node{
    double x,y,k,len;
    inline void init(){
        scanf("%lf%lf",&x,&y);
        k=y/x,x/=1000.0,y/=1000.0,
        len=sqrt(x*x+y*y); 
    }
}c[N];
int T,n;
double a,b,mxv,f;
inline bool ck(double mid){
    double res=0.0;
    for(int i=1;i<=n;++i){
        res+=max(a*mid+b*c[i].k,0.0)*c[i].len;
        if(res+eps>=f) return 0;
    }return 1;
}
inline double calc(double v){
    double res=0.0;
    for(int i=1;i<=n;++i){
        double tmp=a*v+c[i].k*b;
        if(tmp<=eps){
            double vv=(-b*c[i].k)/a;
            vv=min(vv,mxv);
            res+=c[i].len/vv;
        }else{
            if(v<=eps) return 0;
            res+=c[i].len/v;
        }
    }
    return res;
}
inline void sol(){
    double l=0,r=mxv,mid;
    int t=0;
    while(t<1000){
        mid=(l+r)/2;
        if(ck(mid)) l=mid;
        else r=mid;
        ++t;
    } 
    double res=calc(l);
    if(res<=eps) puts("IMPOSSIBLE");
    else printf("%.5lf\n",res);
}
int main(){
    if(fopen("test.in","r")){
        freopen("test.in","r",stdin);
        freopen("test.out","w",stdout);
    }
    scanf("%d",&T);
    while(T--){
        scanf("%lf%lf%lf%lf%d",&a,&b,&mxv,&f,&n);
        for(int i=1;i<=n;++i) c[i].init();
        sol();
    }
}