Browse Category

贪心

POJ 2431 Expedition

一辆卡车要行驶L单位距离,最开始时,卡车上有P单位汽油,每向前行驶1单位距离消耗1单位汽油。如果在途中车上的汽油耗尽,卡车就无法继续前行,即无法到达终点。
途中共有N个加油站,加油站提供的油量有限,卡车的油箱无限大,无论加多少油都没问题。
给出每个加油站距离终点的距离和能够提供的油量,问卡车从起点到终点至少要加几次油?如果不能到达终点,输出-1。

POJ 3617 Best Cow Line

给定长度为N的字符串S,构造一个长度为N的字符串T,并且每次只能对S的首尾字符进行操作,目标是使得构造出的T的字典序尽可能小。
还算简单的贪心问题吧!只要确定好贪心策略,就没有什么问题啦~