PAT 1033 贪心

题目分析：

一道不错的贪心题。

首先看到这个题，我考虑的是区间dp，设dp[i][j]为i点到j点的最少话费，那么如何分解这个问题呢？我初步想的是寻找i到j之间的价格最低的站点，花费最少的钱到达那里，然后加满油，即类似dp[i][j]=dp[i][minst(i,j)]+dp[minst(i,j)][j]。但是这个思路是非常不完善的，dp[i][j]在出发时是不一定加满油的，在划分后的后半段出发时也不一定是加满的，这个加的量多少是无法确定的；此外没有考虑油箱的容量，也不知道某个点是否可达，总之槽点很多。但是这个初步想法为我们提供了一个正确的核心思路：尽量找便宜的地方加油。

一般情况下，我们车里有任意数量的油，从任意站点出发，这些油能够支撑我们到达后面的0个或者多个站点，那么我们的目的就变成了花费尽量少的加油钱到达这些站点中的某一个，然后再考虑。所以贪心策略为：

若当前油量所支撑的可到达的站点中单价有比当前站点的单价低的，那么到达最低的那个站点，然后再考虑；若当前油量所支撑的可到达的站点中单价没有比当前站点的单价低的，那么加到能够到达下一个单价比当前站点单价低的加油站，然后到达那一站；如果不存在这样的加油站，那就加到满油，然后到达下一站，然后再考虑。

这种思路在大体上是正确的，但是其实在情况的划分上还存在不少重复，参考网上的博客，思路可以简化：

对于任意一个站点作为出发点，设其加满油能够到达的距离为“可达距离”，那么就有两种情况。

第一种，可达距离中存在比当前出发站点的单价低的站点，那么只需找到第一个比这个站点单价低的，然后到这个站点的话，路上要加油，只能从开始站点加，因为开始站点是除了目的站点之外单价最低的站点。因此这种情况下只要在开始站点将油加够到达目的站点即可。值得注意的是，根据第二种情况，我们可以得出在本算法中第一种情况下一定要加至少0升油，不存在加负数升油。

第二种，可达距离中不存在比当前出发站点单价低的站点，那么只需找到单价最低的站点，想到达终点至少要跑出可达范围，想跑出这个范围就一定要消耗油箱里的所有油，这些油可以在这个可达范围内的任何站点补充，但是无论在哪里补充，效果都是跑出这个可达范围，区别只是跑到这个可达范围后剩下的油量。如果都要求跑出这个可达范围后刚好把油用完，那么总耗油量是一定的，就是油箱的容量，这些需要的油在最低价格的站点，也就是开始站点进行补充加满即可，这是最低要求下的最优解。但是在跑出这个范围前，我们还有可能在路上的其它站点加点油，让我们跑出去之后还能剩点油，这些在跑出去之前的路上加的油可能比跑出这个范围后再加油划算，但是不管怎么样，出发的站点处加满一定是正确的一步操作。后面路上的站点要不要加呢？只需要让车跑到下一个站点，然后以下一个站点作为起始站点再考虑就行了。当然由于这里中间的站点都能到达当前可达范围的最小价格站点，因此在这些中间站点中都不可能加油，因此直接到这个最小价格站点就可以了，相当于两种情况合二为一。

代码：

#include <bits/stdc++.h>

using namespace std;

const double inf = 100000000.0;

struct station{
    double price;
    double distance;
    bool operator < (const station & a)const{
        return this->distance < a.distance;
    }
};

vector<station> st;

int main(){
    double cmax,d,davg;
    
    int N;
    
    cin>>cmax>>d>>davg>>N;
    
    station s;
    s.price = 0;
    s.distance = d;
    
    st.push_back(s);
    
    for(int i = 1;i <= N;i++){
        cin>>s.price>>s.distance;
        st.push_back(s);
    }
    
    sort(st.begin(),st.end());
    if(st[0].distance != 0){
        cout<<"The maximum travel distance = 0.00"<<endl;
        return 0;
    }
    
    double nowprice = st[0].price,cost = 0.0,nowdis = 0.0,maxdis = 0.0,minprice = inf,disleft = 0.0;
    int minpos = -1;

    while(nowdis < d){
        bool flg = false;
        // 计算可达范围
        maxdis = nowdis + cmax*davg;
        
        // 找到可达范围里的第一个小于当前站点价格的站点
        for(int i = 0;i < st.size();i++){
            if(st[i].distance <= nowdis) continue;
            if(st[i].distance > maxdis) break;
            
            if(st[i].price < nowprice){
                // 按照我们的算法，到达下一个低于当前站点价格的站点，不加油的话不可能还剩下油，即至少要加0升油
                cost += (st[i].distance - nowdis - disleft)*nowprice/davg;
                disleft = 0.0;
                nowdis = st[i].distance;
                nowprice = st[i].price;
                flg = true;
                break;
            }
        }
        
        // 可达范围内没有比当前站点价格高的站点
        if(!flg){
            minprice = inf;
            // 找到价格最低的站点
            for(int i = 0;i < st.size();i++){
                if(st[i].distance <= nowdis) continue;
                if(st[i].distance > maxdis) break;
                
                if(st[i].price < minprice){
                    minprice = st[i].price;
                    minpos = i;
                }
            }
            
            // 假如找到了，那么加满，去可达范围内价格最低的站点
            if(minprice != inf){
                cost += (cmax - disleft/davg)*nowprice;
                disleft = (cmax - (st[minpos].distance - nowdis)/davg)*davg;
                nowprice = st[minpos].price;
                nowdis = st[minpos].distance;
            }
            
            // 假如没找到，说明可达范围内没有任何站点，意味着达不到终点
            if(minprice == inf){
                cout<<"The maximum travel distance = "<<setiosflags(ios::fixed)<<setprecision(2)<<(nowdis+cmax*davg)<<endl;
                return 0;
            }
            
        }
    }
    cout<<setiosflags(ios::fixed)<<setprecision(2)<<cost<<endl;
}

9ms