BZOJ2732/HNOI2011/赛车游戏

Posted on By 二价氢

#题目描述

#做法

看着很像NOI 2012 骑行川藏对吧

但是如果用什么拉格朗日乘数法,调整法,全部复杂了!

我们观察一下题目给的公式

每公里耗油:

这是线性的,所以,对于每段下坡,我们给它加上的初速度

然后下坡和上坡就一样了,上坡和平路的速度都默认为0就好了

然后,我们遍历每一段,给它分配速度,其实是给整条线路分配速度,我们知道,一定有一种方法,使得能匀速行驶完全程(不计下坡预先分配的速度)

所以,就和没啥区别了

#复杂度分析

需要排序处理一下,排序显然是

每次询问,除排序外的时间复杂度为

#AC Code