美文网首页
1033.To Fill or Not to Fill

1033.To Fill or Not to Fill

作者: 81f83b4769e0 | 来源:发表于2016-06-01 21:16 被阅读0次

    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;
                }
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:1033.To Fill or Not to Fill

          本文链接:https://www.haomeiwen.com/subject/exbhdttx.html