一、题目描述
题目描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1D1、汽车油箱的容量CC（以升为单位）、每升汽油能行驶的距离
D2D2、出发点每升汽油价格PP和沿途油站数NN（NN可以为零），油站ii离出发点的距离DiDi、每升汽油价格PiPi（i=1,2,…,Ni=1,2,…,N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
输入格式
第一行，D1D1，CC，D2D2，PP，NN。
接下来有NN行。
第i+1i+1行，两个数字，油站i离出发点的距离DiDi和每升汽油价格PiPi。
输出格式
所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
输入输出样例
输入
275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2
输出
26.95
说明/提示
N≤6,其余数字≤500
二、用到的算法思想
【贪心算法】
三、思路
首先做如下定义：加油站距离数组dis[n+2], 汽油价格数组pri[n+2], 两者一一对应。
接着对这两个数组初始化，dis[0] = 0; pri[0] = p; // 将出发点的距离 0 和 油价p 放入数组
dis[n+1] = d1; pri[n+1] = 0; // 终点的距离 d1, 油价 0 放入数组
将之后输入的N行数据按照距离从小到大排列，需要注意的是，交换距离的时候需要将对应的价格也交换。
那么只需要从距离最小的点开始出发，依次进行计算。
需要注意的地方：1、每次都需要判断是否能够到达下一个加油站，如果无法到达，则直接退出。
2、每次在当前能够走到的最远距离内进行判断，寻找是否有比当前油价更低的加油站。如果没有更低的，价格相等也可以。
3、由于最后一点 pir[n+1] 的油价为0，所以要对其特殊处理。
四、实现代码（C语言）
1、带注释的代码，运行也有输出提示，可以用来纠错。
#include <stdio.h>
#include <stdbool.h> // 洛谷编译器识别 bool 类型需要加入这个头文件
int main() { float d1, c, d2, p; int n, i, j; scanf("%f %f %f %f %d", &d1, &c, &d2, &p, &n); float pri[n+2]; // 价格 float dis[n+2]; // 距离 float minPri, nowDis=0.0, nowOil=0.0; // 最少价格，当前距离, 当前油量 float maxdis; // 能行驶的最大距离 int min;// 最低价格的下标 bool flag = false,is = false; // 当前是否有最优解, 能否到达， 已经到达 pri[0] = p; // 初始点油价为p dis[0] = 0; // 距离为0 dis[n+1] = d1; // 终点距离为D1 pri[n+1] = 0; // 油价为0 float fpri = 0; // 最终价格 for(i = 1; i <= n; i++) { scanf("%f %f",&dis[i], &pri[i]); } /*将价格和距离的数组按照 距离出发点的距离从小到大排序*/ for(i = 1; i <= n; i++) { for(j = i; j <= n; j++) { if(dis[i] > dis[j]) { float td = pri[i]; pri[i] = pri[j]; pri[j] = td; p = dis[i]; dis[i] = dis[j]; dis[j] = p; } } } printf("排序结果为：n价格："); for(i = 0; i <= n+1; i++) { pri[i] = ((int)(100*pri[i] + 0.5))/100.0; printf("%f " ,pri[i]); } printf("n距离："); for(i = 0; i <= n+1; i++) { dis[i] = ((int)(100*dis[i] + 0.5))/100.0; printf("%f " ,dis[i]); } printf("n"); i = 0; j = 0; /*排序完成(冒泡排序，时间复杂度On(^2))*/ while(1) { printf("当前位置：%dn", i); if(i >= n+1) // 已经到达最后一站 { is = true; break; } maxdis = dis[i] + c * d2; if(maxdis < dis[i+1]) // 当前站无法到达下一站 { is = false; break; } flag = false; // 最优标志恢复初始状态 min = i+1; for(j = i+1; j < n+2; j++) // 从当前油站的下一站开始判断 { if(maxdis < dis[j]) // 无法到达该位置的加油站，取消判断 { break; } if(pri[j] <= pri[min] && j < n+1) // 查询此处加油站的价格是否比当前最低价格更低, 并且此处不是终点 { if(pri[j] != pri[min]) { min = j; } if(pri[j] <= pri[i]) // 此地价格是否等于或低于当前油价并且不是终点 { printf("找到了价格更低的加油站：%dn", j); flag = true; break; } } } if(flag) // 能找到比当前更低的地方 { fpri += (dis[min] - dis[i] - nowOil*d2) / d2 * pri[i]; // 只加油到能够到达的那个加油站 i = min; // 到达最低位置的加油站 } else // 找不到更低的 { if(j >= n+2) // 能够到达终点 { printf("找不到更低的加油站，但可以到达终点!n"); fpri = fpri + (dis[n+1] - dis[i] - nowOil*d2) / d2 * pri[i]; nowOil = 0; i = j; // 到达终点 } else // 直接加满 { printf("找不到更低的加油站，也无法到达终点，但找到了最低的加油站位置：%d!n", min); fpri += (c-nowOil)*pri[i]; nowOil = c - (dis[min] - dis[i]) / d2; i = min; // 到达最低位置的加油站 } } printf("当前位置: %d, 当前消耗金钱 is %f, 剩余油量 is %fn", i, fpri, nowOil); } if(!is) { printf("No Solution"); } else { fpri = ((int)(100*fpri + 0.5))/100.0; // 实现四舍五入 printf("%.2f", fpri); } return 0; }
2、纯代码，可直接放入NOIP给的编译器运行
#include <stdio.h> #include <stdbool.h> int main() { float d1, c, d2, p; int n, i, j; scanf("%f %f %f %f %d", &d1, &c, &d2, &p, &n); float pri[n+2]; float dis[n+2]; float nowOil=0.0; float maxdis; int min; bool flag = false,is = false; pri[0] = p; dis[0] = 0; dis[n+1] = d1; pri[n+1] = 0; float fpri = 0; for(i = 1; i <= n; i++) { scanf("%f %f",&dis[i], &pri[i]); } for(i = 1; i <= n; i++) { for(j = i; j <= n; j++) { if(dis[i] > dis[j]) { float td = pri[i]; pri[i] = pri[j]; pri[j] = td; p = dis[i]; dis[i] = dis[j]; dis[j] = p; } } } i = 0; j = 0; while(1) { if(i >= n+1) { is = true; break; } maxdis = dis[i] + c * d2; if(maxdis < dis[i+1]) { is = false; break; } flag = false; min = i+1; for(j = i+1; j < n+2; j++) { if(maxdis < dis[j]) { break; } if(pri[j] <= pri[min] && j < n+1) { if(pri[j] != pri[min]) min = j; if(pri[min] <= pri[i]) { flag = true; break; } } } if(flag) { fpri += (dis[min] - dis[i] - nowOil*d2) / d2 * pri[i]; nowOil += (dis[min] - dis[i]) / d2; nowOil -= (dis[min]-dis[i])/d2; i = min; nowOil -= (dis[min]-dis[i])/d2; i = min; } else { if(j >= n+2) { fpri = fpri + (dis[n+1] - dis[i] - nowOil*d2) / d2 * pri[i]; nowOil += (dis[j] - dis[i]) / d2; i = j; } else { fpri += (c-nowOil)*pri[i]; nowOil = c; nowOil -= (dis[min]-dis[i])/d2; i = min; } } } if(!is) { printf("No Solution"); } else { fpri = ((int)(100*fpri + 0.5))/100.0; printf("%.2f", fpri); } return 0; }
五、完成时间
2021-01-20 15:46:54
零零散散用了近三个小时，快急哭了都，555~~~~~。
下次给思路加上思维导图吧，不然总觉得稀里糊涂的.........
下面是通过成功截图（虽然通过了，但也提交了七八次，甚至可能还有问题，请多加注意~~~~~）
六、补充一些输入与对应的正确输出
输入： 87.75 13.03 5.75 7.29 3 22.10 7.38 24.21 6.81 82.08 6.96 输出： 105.95 粘贴记得去回车和中文字符
输入： 475.6 11.9 27.4 14.98 6 102.0 9.99 220.0 13.29 256.3 14.79 275.0 10.29 277.6 11.29 381.8 10.09 输出 192.15
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
