旅行家的预算题解

本文主要是介绍旅行家的预算题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

通往题目的大门

题目描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（0<=N<=100），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No solution”。

输入格式第1行：5个空格分开的数据，分别表示D1 C D2 P N 第2…N+1行：每行3个空格分开的数据，分别表示油站号i, 该油站距出发点的距离Di，该油站每升汽油的价格Pi
输出格式第1行：一个数据，表示最少费用。

样例输入

275.6 11.9 27.4 2.8 2    
1 102.0 2.9    
2 220.0 2.2

样例输出

26.95

分析

这道题还是有难度的，在与一位大巨佬两个小时的语音通话后，总结出了AC这道题的方法，如下：~~主要是没看懂GM的题解~~
首先，这是一道贪心题：花最少的钱走完全程。现在，我们先来点简单的
改变一下题目，把油箱的容量改为无限，则贪心策略显而易见：

step1.

起点时一定要加油的，每升要用P元。假设中途有三个加油站，且你不想在中途加油，那么你的其实就是每一段都用的P价格的油

start--P--a[1]--P--a[2]--P--a[3]--P--end

如果我告诉你第二个加油站每升只要 P-1 元，你还会傻傻的用上面这个方案吗？我猜不会，你可以一开始就加刚好能到第二个加油站的油，后半程就可以换成 P-1 元的油了，如下图

start--P--a[1]--P--a[2]--（P - 1）--a[3]--（P - 1）--end

是不是赚了？我们把它一推广，就可以得到

step2.

在每个加油站加油只需加到能到达后面油价最低（且比它的油价还低）的加油站即可，若找不到这种加油站，恭喜你，可以准备直达了，中途不用换油，记：在第 i 个加油站加油用了 cost[i] 元，则有

int mi = INT_MAX, v = i;
for(int j = i + 1; j <= n; i++) {    if(a[j].p < mi && a[j].p < a[i].p) {     mi = a[j].p;      v = j    }
}
if(v == i) cost[i] = (d1 - a[i].d) / d2 * a[i].p;
else cost[i] = (a[v].d - a[i].d) / d2 * a[i].p;

不一定对哈，毕竟没认真实现过

前面的那么多都是引入，开始正题：
引入已经说的很清楚了，在这道题的正解中，我们只是多加入了一个判断无解：当在一个加油站加满油还不能到达下一个加油站时，旅行失败。

还有就是因为油箱容量有上限，所有我们还需要看一下当前油箱省的油最远能到哪一个加油站，确定选最小值的距离范围
我们还考虑了一下，距离远近顺序的问题，就是一号加油站可能在二号加油站后面，所以先有一次排序。但最后发现，数据中没有这一情况。

根据思路不难得出

AC代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;const int MAXN = 105;
struct data { // 结构体 int i;double di, pi;
//	油站 i 离出发点的距离 Di, 每升汽油价格 Pi
} a[MAXN];
bool cmp(data x, data y) { // sort cmp 函数 return x.di < y.di;
}int main() {double d1, c, d2, p;int n;	scanf ("%lf %lf %lf %lf %d", &d1, &c, &d2, &p, &n); 
//	给定两个城市之间的距离 D1, 汽车油箱的容量 C, 每升汽油能行驶的距离 D2, 出发点每升汽油价格 P和沿途油站数 N a[0].di = 0, a[0].pi = p;for (int i = 1; i <= n; i++) {scanf ("%d %lf %lf", &a[i].i, &a[i].di, &a[i].pi);a[i].di /= d2;}a[n + 1].di = d1 / d2; n += 2;sort(a, a + n, cmp);for (int i = 1; i < n; i++) if (a[i].di - a[i - 1].di > c) { // 判断无解 printf("No solution");return 0;}double rest = 0, cost;for (int i = 0; i < n; i++) {int min_pos = i; // 价格最低的加油站的位置 double min_val = a[i].pi; // 价格最低的加油站的价格 int j, k;
//  j 剩余油量能到达的最远的加油站 
//  k j + 1 到 n - 1 中第一个比 minpos 便宜的点 for (j = i + 1; j < n && a[j].di - a[i].di <= rest; j++)if (min_val < a[j].pi)min_val = a[j].pi, min_pos = j;
//	求出价格最低的加油站的相关信息 for (k = j; k < n; k++)if (a[k].pi < min_val)break;if (k == n) // 判断能否到终点 k = n - 1;rest -= (a[min_pos].di - a[i].di); double end = (a[k].di - a[min_pos].di); 
//  rest 第一部分的路程
//  end  第二部分的路程 if (end <= c) {  // 能直接到达 Kcost += (end - rest) * a[min_pos].pi; // 加油 if (k == n - 1)break;elsei = k - 1, rest = 0; // 更新 } else {  // 否则加满油cost += (c - rest) * a[min_pos].pi;i = min_pos;  rest = c; rest -= a[i + 1].di - a[i].di;}}printf("%.2lf\n", cost);return 0;
}