1033.To Fill or Not to Fill

题目分析

Input：
第一行：Cmax D Davg N
接下来的N行：Pi Di
Output：（accurate up to 2 decimal place）
Case1：minimum price
Case2：The maximum travel distance = xxx

贪心策略

• 在distance=0的地方必须有加油站
• 在distance=D的地方（终点），油箱里油的剩余量必须为0
• 假设某一站为A，则如果在A加满油，能行驶的最远距离为maxDis=Cmax*Davg
• 使用leftGas变量来记录剩余油量

1. 在A.distance~A.distance+maxDis之间寻找第一个比A便宜的站，如果找到，记为B，则在A加刚好行驶至B的油量
2. 若没有符合情况1的站，但是有终点，则在A加刚好可以行驶至终点的油量
3. 若没有符合情况1和情况2的站，则找一个站C，C.price在相应范围内最小，在A加满油，行驶至C
4. 不是情况1、2、3的任何一种情况，则行驶的最大距离为A.distance+maxDis

C++源码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

#define INF 99999

typedef struct Station
{
    double price;
    double distance;
}Station;

// the pointer tempA can point to a value of any type but the value must be a constant
int cmp(const void* tempA,const void* tempB)
{
    Station *a = (Station*)tempA;
    Station *b = (Station*)tempB;
    return a->distance - b->distance;
}

int main()
{
    int N;
    double Cmax, D, Davg;
    cin>>Cmax>>D>>Davg>>N;
    Station *stations = new Station[N+1];
    for(int i = 0; i < N; i++)
    {
        cin>>stations[i].price>>stations[i].distance;
    }
    stations[N].price = INF;
    stations[N].distance = D;
    qsort(stations, N+1, sizeof(Station), cmp);

    // if there is no station at the beginning
    if(stations[0].distance != 0)
    {
        cout<<"The maximum travel distance = 0.00"<<endl;
        return 0;
    }

    double maxDis = Cmax * Davg;
    double minPrice = 0;
    double leftGas = 0;
    // station index indicates where the car is now, the initial value is 0
    int index = 0;

    while(index != N)
    {
        int intermedia = -1;
        int caseFlag = 0;
        int boundFlag = -1;
        for(int i = 0; i <= N; i++)
        {
            if(stations[index].distance <= stations[i].distance && stations[i].distance <= stations[index].distance + maxDis)
            {
                boundFlag = i;
                if(stations[i].price < stations[index].price)
                {
                    if(intermedia == -1)
                    {
                        intermedia = i;
                        caseFlag = 1;
                    }
                }
            }
        }

        if(caseFlag == 1)
        {
            minPrice = minPrice + stations[index].price * (((stations[intermedia].distance - stations[index].distance) / Davg) - leftGas);
            leftGas = 0;
            index = intermedia;
        }
        else if(caseFlag != 1 && stations[index].distance <= D && D <= stations[index].distance + maxDis)
        {
            caseFlag = 2;
            minPrice = minPrice + stations[index].price * ((D - stations[index].distance) / Davg - leftGas);
            printf("%.2lf\n", minPrice);
            leftGas = 0;
            index = N;
            return 0;
        }
        else if(caseFlag != 1 && caseFlag != 2)
        {
            if(boundFlag == index)
            {
                // caseFlag = 4;
                printf("The maximum travel distance = %.2lf\n", stations[index].distance + maxDis);
                return 0;
            }
            else
            {
                caseFlag = 3;
                double tempMinPrice = stations[index+1].price;
                for(int i = index + 1; i <= boundFlag; i++)
                {
                    if(stations[i].price <= tempMinPrice)
                    {
                        tempMinPrice = stations[i].price;
                        intermedia = i;
                    }
                }
                minPrice = minPrice + stations[index].price * (Cmax - leftGas);
                leftGas = Cmax - (stations[intermedia].distance - stations[index].distance) / Davg;
                index = intermedia;
            }
        }
    }
}