注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2328 (hnoi 2011) 赛车游戏  

2013-02-15 01:42:18|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

不知道拉格朗日乘数也是没关系的啦

直接贪心就可以了

我们给每一段路一个初速度

当这是上坡路或平路时,初速度为0

当这是下坡路时,初速度为-bs/a

这就是在耗油最小的情况下的最快了,我们完全可以理解为这是这段路速度的下限,因为只要有段路速度低于其初速度,将其加为初速度耗油不会增加同时更快。

同时那个max(av+bs,0)也可以无视掉,直接套av+bs即可

接下来我们还要证明一个东西

在某段路上以v1行驶,某段路上以v2行驶,不考虑初速度问题,必然有种方案为在两段路上都以v速度行驶更优。

即:

s1/v1+s2/v2>=(s1+s2)/v

s1*(av1+bs)+s2*(av2+bs)=(s1+s2)*(av+bs)->s1*v1+s2*v2=(s1+s2)*v

存在v同时满足两个式子

证明是这样的:解第一个不等式得到v>=一个分式,解第二个等式得到v=一个分式然后发现第一个分式大于第二个分式

再与之前的结论搭配,就有了这样一个算法

按初速度排好序,那么速度就绝不能比之前低,又由于速度相同比较好,所以我们希望最小的跟第二小的一样,然后又跟第三小的一样

想象一下就发现,我们是在模拟一个往阶梯灌水的过程

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define eps 1e-13
#define MAXN 10010
using namespace std;
int dcmp(double p)
{
    if(fabs(p)<eps)  return 0;
    return p>eps?1:-1;
}
int n;
double vmax,oil,a,b;
bool mark;
struct Node
{
    double deltax,deltay,k,speed,dis;
    friend bool operator < (const Node &a,const Node &b){  return a.speed<b.speed;  }
}road[MAXN];
void read()
{
    mark=false;
    scanf("%lf %lf %lf %lf %d",&a,&b,&vmax,&oil,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf %lf",&road[i].deltax,&road[i].deltay);
        road[i].deltax/=1000,road[i].deltay/=1000;
    }
}
void First_Speed()
{
    for(int i=1;i<=n;i++)
    {
        road[i].k=road[i].deltay/road[i].deltax;
        road[i].dis=sqrt(road[i].deltax*road[i].deltax+road[i].deltay*road[i].deltay);
        if(dcmp(road[i].k)>=0)  road[i].speed=0,mark=true;
        else road[i].speed=min(vmax,-b*road[i].k/a);
    }
}
void solve()
{
    for(int i=1;i<=n;i++)
        oil=oil-max(0.0,b*road[i].k+a*road[i].speed)*road[i].dis;
    if(dcmp(oil)<0||(!dcmp(oil)&&mark))
    {
        printf("IMPOSSIBLE\n");
        return ;
    }
    sort(road+1,road+n+1);
    double nowd=road[1].dis,nowv=road[1].speed;
    for(int i=2;i<=n;i++)
    {
        double delta_oil=(road[i].speed-nowv)*a*nowd;
        if(dcmp(oil-delta_oil)<=0)
        {
            nowv=nowv+oil/a/nowd;
            double ans=nowd/nowv;
            for(int j=i;j<=n;j++)
                ans=ans+road[j].dis/road[j].speed;
            printf("%.5lf\n",ans);
            return ;
        }
        nowv=road[i].speed,nowd+=road[i].dis,oil-=delta_oil;
    }
    nowv=min(vmax,nowv+oil/a/nowd);
    printf("%.5lf\n",nowd/nowv);
}
int main()
{
    int test;
    for(scanf("%d",&test);test>=1;test--)
    {
        read();
        First_Speed();
        solve();
    }
    return 0;
}


  评论这张
 
阅读(685)| 评论(5)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017