首页 > 代码库 > codeforces Codeforces Round #380 (Div. 1, Rated, Based on Technocup 2017 - Elimination Round 2)// 二分的题目硬生生想出来ON的算法

codeforces Codeforces Round #380 (Div. 1, Rated, Based on Technocup 2017 - Elimination Round 2)// 二分的题目硬生生想出来ON的算法

A. Road to Cinema

很明显满足二分性质的题目。

题意:某人在起点处,到终点的距离为s。 汽车租赁公司提供n中车型,每种车型有属性ci(租车费用),vi(油箱容量)。 车子有两种前进方式 :①. 慢速:1km消耗1L汽油,花费2分钟。 ②.快速:1km消耗2L汽油,花费1分钟。 路上有k个加油站,加油不需要花费时间,且直接给油箱加满。 问在t分钟内到达终点的最小花费是多少?(租车子的费用)  若无法到达终点,输出-1

不谈二分的写法.. 我们考虑离散化可修改的点  和限制的点位置   如果发现有限制就结束。那么思路很简单了。一个数组存分段的最大耗油量。ans = 跑最快情况下的最小时间的最大值。依次牺牲多余时间减小耗油即可。取个max就可以了。

算上排序的时间依旧是klogk+n。不好写坑点多。。

开了流量写CF.... 500MB没了......  我R   算了算了不写....

 

codeforces Codeforces Round #380 (Div. 1, Rated, Based on Technocup 2017 - Elimination Round 2)// 二分的题目硬生生想出来ON的算法