这题妥妥的贪心嘛, 我们整理下题目:
首先对于每一个加油站来说, 我们可以知道的信息是到上一个加油站(或起点)的距离, 以及本加油站的油钱. 对于车来说我们知道车最多能加多少油, 以及每升油能开多远.
最终要得到的结果是这辆车最少能花多少钱, 或者这辆车半路就没油了.
那么我们假设我们现在在任意一个加油站(假设是第 $i$ 个), 为了节省任意油费, 自然要选最便宜的油, 到开到这个加油站为止, 我们可以加油的点有 $i$ 个(包括起点), 我们需要选取其中油费最便宜的加足够开到下一个加油站的油即可.
但是需要额外考虑的一个问题就是油箱是有大小的(当然加油站你可以视为无限油桶), 也就是说一个加油站最多最多也只能加你车油箱的容量的油(不然就是犯规操作的了嘛). 假如说这个加油站以及加过了一油箱的油了, 那么车子在那个加油站就不可能再加油了. 我们就要考虑到另一个加油站加油了, 而那个加油站就是除去这个加油站以外的油钱最便宜的加油站了.
当然这个前提是在有别的可加油的加油站的情况的, 如果没有了呢, 就说明没地方加油了, 没油了, 车就开不了了, 直接输出”No Solution”
然后整理完解法后我们发现, 所有的基于当前的加油站的运算和之后的数据完全无关, 只和之前的数据有关, 所以我们采取边输入, 边运算的方法.
由于我们的数据都是依次输入得到的, 所以我们采用插入排序, 用来得到最便宜的加油站, 如果这个加油站不能再加油了, 我们就删去这一项.
注意: 最后一段路(最后一个加油站(或起点)到终点)是没有输入的(终点的距离就是路程的距离), 所以我们要单独拿出来再运算, 不能漏掉.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #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);
}
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;
}
|
