• Greedy method:

condition 1: you can't start the engine, there is no gas station at the beginning
condition 2: you can't arrive at the end, means there are two neiboring gas staion ar> e too far away from each other (the distance > max tank capacity * average distance > per unit gasoline)
condition 3: when you arrive at a gas station, you need to check all the other station> s you can reach from where you are now one by one,

(i)once you could find a cheaper one (not the cheapest one!!!), fiil the tank so that you can reach there and run out of all the gasoline.

(ii)if you can't find a cheaper one, just fill up the tank.

• Code:

//  Copyright © 2018 Fangzhou Ai. All rights reserved.

//  Copying it directly is cheating if this is your homework

#include

int max_capacity;

int distance;

float avg_distance;

int total_number;

float gas_station[501][2];

float money;

void sortseq(void);//sort by distance

float greedy(void);

int main()

{

    int i;

    //input

    scanf("%d%d%f%d",&max_capacity,&distance,&avg_distance,&total_number);

    for(i=0;i

        scanf("%f%f",&gas_station[i][0],&gas_station[i][1]);



    //sort the sequence order by distance

    sortseq();

    if(gas_station[0][1]>0||total_number<1)

    {printf("The maximum travel distance = 0.00");return0;}



    for(i=0;i

    {

        if(gas_station[i+1][1]-gas_station[i][1]>max_capacity*avg_distance)

            break;

    }

    //check if it could reach the destination, if it can't, calculate the max distance

    if(gas_station[i+1][1]-gas_station[i][1]>max_capacity*avg_distance||distance-gas_station[total_number-1][1]>max_capacity*avg_distance)

    {

        printf("The maximum travel distance = %.2f",gas_station[i][1]+max_capacity*avg_distance);

    }

    else

    {

        //greedy method

        // set the destination as the cheapest gsa station to simplify the procedure

        gas_station[total_number][0]=-1;

        gas_station[total_number][1]=distance;

        money=greedy();

        printf("%.2f",money);


    }

    return0;

}