题解 P1016 【旅行家的预算】妥妥的贪心

Alex_Cui

2019-03-13 14:51:14

Solution

这题妥妥的贪心嘛, 我们整理下题目: 首先对于每一个加油站来说, 我们可以知道的信息是到上一个加油站(或起点)的距离, 以及本加油站的油钱. 对于车来说我们知道车最多能加多少油, 以及每升油能开多远. 最终要得到的结果是这辆车最少能花多少钱, 或者这辆车半路就没油了. 那么我们假设我们现在在任意一个加油站(假设是第 $i$ 个), 为了节省任意油费, 自然要选最便宜的油, 到开到这个加油站为止, 我们可以加油的点有 $i$ 个(包括起点), 我们需要选取其中油费最便宜的加足够开到下一个加油站的油即可. 但是需要额外考虑的一个问题就是油箱是有大小的(当然加油站你可以视为无限油桶), 也就是说一个加油站最多最多也只能加你车油箱的容量的油(不然就是犯规操作的了嘛). 假如说这个加油站以及加过了一油箱的油了, 那么车子在那个加油站就不可能再加油了. 我们就要考虑到另一个加油站加油了, 而那个加油站就是除去这个加油站以外的油钱最便宜的加油站了. 当然这个前提是在有别的可加油的加油站的情况的, 如果没有了呢, 就说明没地方加油了, 没油了, 车就开不了了, 直接输出"No Solution" 然后整理完解法后我们发现, **所有的基于当前的加油站的运算和之后的数据完全无关, 只和之前的数据有关**, 所以我们采取边输入, 边运算的方法. **由于我们的数据都是依次输入得到的**, 所以我们采用**插入排序**, 用来得到最便宜的加油站, 如果这个加油站不能再加油了, 我们就删去这一项. 注意: 最后一段路(最后一个加油站(或起点)到终点)是没有输入的(终点的距离就是路程的距离), 所以我们要单独拿出来再运算, 不能漏掉. ```cpp #include <iostream> #include <iomanip> #include <list> struct Station { double added_oil; // 该加油站加过的油 double oil_price; // 该加油站的汽油单价 }; void insert(std::list<Station> &list, double oil_price) { for (std::list<Station>::iterator iter = list.begin(); iter != list.end(); ++iter) { if (iter->oil_price > oil_price) { list.insert(iter, { 0.0, oil_price }); return; } } list.push_back({ 0.0, oil_price }); } int main() { double d1, d2, c, p; int n; std::cin >> d1 >> c >> d2 >> p >> n; std::list<Station> stations; stations.push_back({ 0.0, p }); double distance, oil_price, last_distance = 0.0, oil_require, money = 0.0, oil_remaining; std::list<Station>::iterator iter; for (int i = 1; i <= n; ++i) { std::cin >> distance >> oil_price; oil_require = (distance - last_distance) / d2; // 需要的油量 iter = stations.begin(); while (oil_require) { oil_remaining = c - iter->added_oil; if (oil_require < oil_remaining) { // 当前最便宜的加油站可加的油还足够加 iter->added_oil += oil_require; money += oil_require * iter->oil_price; break; } else { // 不够加了 oil_require -= oil_remaining; // 缺少的油 money += oil_remaining * iter->oil_price; stations.erase(iter); // 删除当前选择的加油站 if (stations.empty()) { // 没有可用的加油站 std::cout << "No Solution" << std::endl; return 0; } iter = stations.begin(); } } last_distance = distance; insert(stations, oil_price); } // 这一段和上面for一样, 唯一的区别就是没有输入, 主要是我懒得封装一个函数传参了, 就直接复制了 oil_require = (d1 - last_distance) / d2; iter = stations.begin(); while (oil_require) { oil_remaining = c - iter->added_oil; if (oil_require < oil_remaining) { iter->added_oil += oil_require; money += oil_require * iter->oil_price; break; } else { oil_require -= oil_remaining; money += oil_remaining * iter->oil_price; stations.erase(iter); if (stations.empty()) { std::cout << "No Solution" << std::endl; return 0; } iter = stations.begin(); } } std::cout << std::setprecision(2) << std::fixed << money << std::endl; return 0; } ```