POJ2431 Expedition

题目很简单,写这个的目的是,我以前做不来,2333

一辆卡车形式L单位距离,开始的时候开车时有P单位的汽油,一个单位距离耗费一个单位汽油,途中有N个加油站,第i个加油站在距离起点A_i单位距离的地方,可以最多给汽车加B_i单位的汽油,车的油箱无限大,问到达终点最少加多少次油。

赤裸裸的贪心,因为油箱无限大,所以我们可以这么认为,我们路过一个加油站之后,我们在之后的路上随时可以选择加那个加油站的油,而且肯定是一次加完B_i,所以我们从汽车初始状态开始开,到没油了,看看路上路过有加油站没,选路过过油最多的,加上,继续这样。最后加油次数一定是最少的。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目: DescriptionA group of cows grabbed a truck and ventur...
    科学旅行者阅读 587评论 0 0
  • 2014年2月14日,双节,国内元宵节,国外情人节。 本身对国外的情人节不太感冒,加之八年的婚姻生活,早就对这个洋...
    万煜阅读 385评论 0 2
  • 那一群人里面,有昂首阔步的,有高谈阔论的,而最无精打采的那个就是我。我走着,思索着,迎面走来的小孩用稚嫩的声音说道...
    奔跑的葱爆肉阅读 947评论 0 2
  • 【十三】男生女生变 我下车后,走进商场,避开商场里的摄像头,来到了商场里的大卖场。 打开一个大卖场门口的储物柜,拿...
    米铺阅读 19,962评论 34 20