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

2019-03-13 14:51:14


这题妥妥的贪心嘛, 我们整理下题目:

首先对于每一个加油站来说, 我们可以知道的信息是到上一个加油站(或起点)的距离, 以及本加油站的油钱. 对于车来说我们知道车最多能加多少油, 以及每升油能开多远.

最终要得到的结果是这辆车最少能花多少钱, 或者这辆车半路就没油了.

那么我们假设我们现在在任意一个加油站(假设是第 $i$ 个), 为了节省任意油费, 自然要选最便宜的油, 到开到这个加油站为止, 我们可以加油的点有 $i$ 个(包括起点), 我们需要选取其中油费最便宜的加足够开到下一个加油站的油即可.

但是需要额外考虑的一个问题就是油箱是有大小的(当然加油站你可以视为无限油桶), 也就是说一个加油站最多最多也只能加你车油箱的容量的油(不然就是犯规操作的了嘛). 假如说这个加油站以及加过了一油箱的油了, 那么车子在那个加油站就不可能再加油了. 我们就要考虑到另一个加油站加油了, 而那个加油站就是除去这个加油站以外的油钱最便宜的加油站了.

当然这个前提是在有别的可加油的加油站的情况的, 如果没有了呢, 就说明没地方加油了, 没油了, 车就开不了了, 直接输出"No Solution"

然后整理完解法后我们发现, 所有的基于当前的加油站的运算和之后的数据完全无关, 只和之前的数据有关, 所以我们采取边输入, 边运算的方法.

由于我们的数据都是依次输入得到的, 所以我们采用插入排序, 用来得到最便宜的加油站, 如果这个加油站不能再加油了, 我们就删去这一项.

注意: 最后一段路(最后一个加油站(或起点)到终点)是没有输入的(终点的距离就是路程的距离), 所以我们要单独拿出来再运算, 不能漏掉.

#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;
}