题目描述

1033 To Fill or Not to Fill （25 分)
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.

Input Specification:
Each input file contains one test case. For each case, the first line contains 4 positive numbers: C
max
(≤ 100), the maximum capacity of the tank; D (≤30000), the distance between Hangzhou and the destination city; D
avg
(≤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: P
i
, the unit gas price, and D
i
(≤D), the distance between this station and Hangzhou, for i=1,⋯,N. All the numbers in a line are separated by a space.

Output Specification:
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.

Sample Input 1:
50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300
Sample Output 1:
749.17

Sample Input 2:
50 1300 12 2
7.10 0
7.00 600
Sample Output 2:
The maximum travel distance = 1200.00

参考代码

#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

const int INF = 100000000;

struct station
{
    //油价和加油站距离杭州的距离
    double p;
    double D;
};

int cmp(station s1,station s2)
{
    if(s1.D != s2.D) return s1.D < s2.D;
    return s1.p <= s2.p;
}

int main()
{
    //cmax最大油量，d杭州与目标城市距离，
    //davg每单位的油，车能行驶的距离
    //N加油站个数
    double cmax,D,Davg;
    int N;
    scanf("%lf %lf %lf %d",&cmax,&D,&Davg,&N);
    double DMAX = cmax * Davg; //满油状态最大行驶距离
    station st[N];
    for(int i=0;i<N;i++){
        scanf("%lf %lf",&st[i].p,&st[i].D);
    }
    //按距离将汽油站从近到远排序
    sort(st,st + N,cmp);
    //如果第一个加油站不在原点
    if(st[0].D != 0.0)
    {
        printf("The maximum travel distance = 0.00\n");
        return 0;
    }

    double X = 0,P = 0; //最大可行驶的距离和总价格


    //能到达情况下消耗的油量
    double c = D / Davg;
    double cleft = 0;

    int i = 0;
    while(i<N)
    {
        //定义当前站和下一站
        int now = i,next;
        //寻找DMAX范围内比当前加油站便宜的加油站
        double MIN = INF,near = 0,index = 0;
        for(int j=i+1;j<N;j++)
        {
            if(st[j].D - st[i].D <= DMAX )
            {
                if(st[j].p < st[i].p)
                {
                    near = j;
                    MIN = st[j].p;
                    break;
                }
                //找DMAX范围内价格最小的加油站
                if(st[j].p < MIN)
                {
                    index = j;
                    MIN = st[j].p;
                }

            }

        }
        if(near == 0)
        {//策略3：没有找到DMAX范围内的加油站，则行驶加满油的距离，结束算法
            if(index == 0)
            { // 没有加油站
                //若处于加油站最后一站
                if(cmax * Davg >= D - X )
                {
                    P += ((D-X) / Davg - cleft) * st[i].p;
                    next = -1;
                }
                else{
                    X += DMAX;
                    break;

                }
            }
            else
            {//策略2：如果找不到油价比当前油价低的加油站，则寻找DMAX范围内油价最低的加油站，在当前加油站加满油前往
                //判断加满油是否能到达终点
                if(cmax * Davg >= D-X)
                {
                    P += ((D-X) / Davg - cleft) * st[i].p;
                    next = -1;
                    // printf("1\n");
                }
                else{
                    //当前为i，下一站为index
                    P += (cmax - cleft) * st[i].p; // 更新价格
                    cleft = cmax;
                    next = index;
                }
            }
        }
        else
        {//策略1:寻找距离当前加油站最近的油价低于当前油价的加油站，加恰好能够到达该加油站的油前往
            //如果找到比当前加油站便宜的，去near
            next = near;
            //当前剩余cleft的油,油不够了
            if(cleft < (st[next].D - st[now].D) / Davg)
            {
                P += ((st[next].D - st[now].D) / Davg - cleft) * st[i].p;
                cleft = (st[next].D - st[now].D) / Davg;
            }
        }

        //去下一战
        //如果下一站为终点站
        if(next == -1)
        {
            X = D;
            break;
        }

        //更新行驶距离
        X += st[next].D - st[i].D;
        //更新油量
        cleft -= (st[next].D - st[i].D) / Davg;
        i = next;
    }
    if(X < D)
    {
        printf("The maximum travel distance = %.2f",X);
    }
    else
        printf("%.2f",P);
}