[NOIP1999 提高组] 旅行家的预算（C++，贪心）

题目描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离 $D_1$、汽车油箱的容量 $C$（以升为单位）、每升汽油能行驶的距离 $D_2$、出发点每升汽油价格$P$和沿途油站数 $N$（$N$ 可以为零），油站 $i$ 离出发点的距离 $D_i$、每升汽油价格 $P_i$（$i=1,2,\dots ,N$）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 No Solution。

输入格式

第一行，$D_1$，$C$，$D_2$，$P$，$N$。

接下来有 $N$ 行。

第 $i+1$ 行，两个数字，油站 $i$ 离出发点的距离 $D_i$ 和每升汽油价格 $P_i$。

输出格式

所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 No Solution。

样例 #1

样例输入 #1

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

样例输出 #1

26.95

提示

$N\le 6$，其余数字$\le 500$。

解题思路：

一道贪心题目

$loop$的大致流程是这样的：

1.从当前点出发，检查能够到达的加油站

2.有两种情况：

(1)检查所有的油站后，发现当前油站是最便宜的

加满油，开到下一个油站

(2)找到更便宜的油站（且最近的）

直接加油到达，保证油量到达时为$0$，即刚好到达

所以$loop$实际上就是检查->加油->下一个循环

然后需要处理几个特殊情况：

1.检查油站阶段，当前油站即是最后一个油站，直接判断能否到达终点，然后输出结果

2.检查油站阶段，距离过远而无法到达下一个加油站，输出No Solution

3.如果当前油站即是最便宜的加油站，判断能否直接到达终点

#include <iostream>
#include <iomanip>
using namespace std;
const int max_n = 6;double price[max_n + 1];
double loca[max_n + 1];
double d1, c, d2;
int n;int main() {cin >> d1 >> c >> d2;cin >> price[0] >> n;//将起点看作一个加油站for (int i = 1; i <= n; i++) {cin >> loca[i] >> price[i];}const double max_len = c * d2;//最大行驶距离double cur_fuel = 0.0;//当前的油量int cur_index = 0;//当前的位置double sum = 0.0;//总花费while (true) {//选择便宜的加油站（除了起点）int i = cur_index + 1;int min_index = cur_index + 1;int far = loca[cur_index] + max_len;//特判if (i > n) {//最后一个油站if (far >= d1) {double needed = (d1 - loca[cur_index]) / d2 - cur_fuel;sum += price[cur_index] * needed;break;}else {//不能到达终点cout << "No Solution" << endl;return 0;}}else if (loca[cur_index + 1] > far) {//无法到达下一个油站cout << "No Solution" << endl;return 0;}while (loca[i] <= far && i <= n) {if (price[min_index] > price[i]) {//找出能到达的加油站中最便宜的min_index = i;}if (price[min_index] < price[cur_index]) {//如果比起点更便宜，则选择该加油站min_index = i;break;}i++;}//加油if (price[min_index] > price[cur_index]) {//起点更便宜//判断是否能到达终点if (far >= d1) {double needed = (d1 - loca[cur_index]) / d2 - cur_fuel;sum += price[cur_index] * needed;break;}//未到达终点double needed = c - cur_fuel;//加满sum += price[cur_index] * needed;//前往下一地点cur_fuel = c - (loca[min_index] - loca[cur_index]) / d2;cur_index = min_index;}else {//找到更便宜的油站double needed = (loca[min_index] - loca[cur_index]) / d2 - cur_fuel;sum += price[cur_index] * needed;cur_fuel = 0;//刚好到达cur_index = min_index;}}cout << setiosflags(ios::fixed) << setprecision(2) << sum << endl;return 0;
}