# Alex_Cui 的博客

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

posted on 2019-03-13 14:51:14 | under 题解 |

#include <iostream>
#include <iomanip>
#include <list>

struct Station {
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) {
if (oil_require < oil_remaining) { // 当前最便宜的加油站可加的油还足够加
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) {
if (oil_require < oil_remaining) {
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;
}