本文共 3082 字，大约阅读时间需要 10 分钟。

Codeup小白掉坑经验总结之 To Fill or Not to Fill id=2031

• 题目如下
  2031: To Fill or Not to Fill
  时间限制: 1 Sec 内存限制: 32 MB
  献花: 66 解决: 19

题目描述

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

输入

Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; Davg (<=20), the average distance per unit gas that the car can run; and N (<= 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi, the unit gas price, and Di (<=D), the distance between this station and Hangzhou, for i=1,…N. All the numbers in a line are separated by a space.

输出

For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print “The maximum travel distance = X” where X is the maximum possible distance the car can run, accurate up to 2 decimal places.

样例输入

59 525 19 2 3.00 314 3.00 0 样例输出 82.89

首先，题目的意思是，你从杭州到某个城市，然后路上有很多个加油站，每个加油站的油价可能相同也可能不同，给你加油站距离杭州的位置和油价，以及你的车的油箱的容量，还有每单位油可以行驶的公里数，如果汽车可以行驶到目的地，那么求出最少需要多少油费，如果行驶不到目的地，那么就输出最远的行驶距离，如果起点没有加油站，输出最大距离为0.00。

这题真的挺难的，至少以现在的我的水平感觉是这样。。。算法思想就构造不出来，不知道应该怎样计算，大概我就是个辣鸡…(｡_｡)

参考晴天宝典的算法思想之后，我才算是知道了怎么做，具体算法思想我按照自己的理解通俗的叙述一下

首先，将输入的加油站按照距离从小到大进行排序，如果最小的那个距离不为0，直接输出最大距离为0.00

如果为0，那么将油价为0，距离等于杭州到目的地的距离的伪加油站N放到刚才排完序的加油站的最后一个位置，然后根据下面几种情况，车一点点的向前进

刚开始，车当前在一个加油站now，在当前站加满油可以行驶到的距离内进行搜寻，搜寻有没有比这个站的油价更便宜的加油站next。

如果有next，那么在now站加足够到next站的油就行了，然后当前站就变成了next，再进行循环判断； 如果没有next，那么在当前站加满油可以行驶到的距离内进行搜寻，搜寻这些加油站里价钱最小的加油站min（除了now站）； 如果有min，就在now站加满油，前往min站，然后再进行循环判断； 如果在当前站可以行驶到的范围内没有加油站，那么结束算法，能行驶的最大距离为当前加油站的距离加上满油状态下能行驶的距离。

循环中间用一个变量来记录当前站，循环结束时，当前站如果等于N，那么说明到达了目的地，输出计算的总油费，当前站如果小于N那么说明无法到达目的地，那么输出最大距离。

实现的代码如下：

#include 
   
    #include 
    
     using namespace std;struct station{    double price;    double dis;}s[510];int cmp(station a,station b){    return a.dis
     
      dis) break;                if(curlen>=s[i].dis&&curlen<=s[i].dis+len)                {                    int first=0,min=i;                    for(int j=i;j<=n;j++)                    {                        if(curlen>=s[j].dis&&curlen<=s[j].dis+len)                        {                            if(s[j].price
      
       s[j].price)                            {                                min=j;                            }                        }                        else break;                    }                    if(first!=0)                    {                        double need=(s[first].dis-s[pre].dis)/davg;                        if(tank
      
     
    
   

代码是我参考晴天宝典的思想自己写的，最后没跑成功然后参考了一下书上的代码进行的debug，反正。。。考试如果出这种题目，我怕就直接GG了。。。不过，毕竟是小白嘛~慢慢积累经验就能成为dalao了，小小的失败不怕不怕，继续加油！！！(ง •̀_•́)ง

转载地址：https://meteorrain.blog.csdn.net/article/details/79068208 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！