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

Road to Peak of OI

唯有魔,不听教会,争渡向前.

 
 
 

日志

 
 

[HNOI2011]赛车游戏 题解  

2014-05-10 16:22:01|  分类: OI |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
被精度卡了一上午,不爽

首先我不知道考场上别人怎么做的,好像有贪心算法的样子,不过我写的还是拉格朗日乘数法...

首先,我们发现,下坡路和上坡路不是很和谐,因为下坡路有一个初始速度,不妨设为sv[],有sv[i] = k[i] * b / a,然后上坡路和平路的初始速度就是0。因为下坡路的能量消耗如果是负数,根据题意会被认为是0,这样显然不是最优解,所以我们假设一开始就将这些能量填充到这些下坡路上去。这样的话,他们的速度分配量的下界就都是0的。接着我们发现,有一个速度上界vmax,这也不是很愉悦,先不管这个条件。


[HNOI2011] 赛车游戏 题解 - bill125 - Road to Peak of OI
 
接着,我们观察一下↑这个式子,他说明了最优策略是在每条路上都用相同的速度跑。
那么,可以想象,我们的分配是保证v'i尽量的平均,那么最终就是找到那么一个v,在每条v>svi的路上都用v的速度跑,且使用的能量<=f。
这可以用普通的二分λ的思路去做,也可以直接去求这个v。(我猜贪心就是用了一个很神的方法去求v)
当然,如果最终的答案中的某个v'i < svi那么,我们当然还是采用svi更妥当,因为用svi速度也不消耗能量,时间一定比原来更优。(这个点比较容易错,反正我一开始写的时候没考虑这个,怒爆一零)
借用@ydc的描述,如果感性地去理解这件事情,这个策略就像是浇水一样,先灌给位置低的部分,最后保证所有的地方水位一致。

最后,是精度的问题,这个题的f对精度要求很高,我看到有一个点读入的f的精度就有1e-8,而且这个f是<2e-3的,感觉出题人非常的不友善= =。二分的话,区间长度要设置的小一点,@Mektpoy告诉我,这个时候限制二分的次数比较安全,我觉得他说的非常有道理,因为我由于二分的精度原因T了一早上,后来对着数据调了好久,才把精度改对了,如果直接限制次数的话,怎么写都不会有问题。

http://ideone.com/ONiFhF
  评论这张
 
阅读(235)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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