题解 P1016 【旅行家的预算】

· · 题解

这道题贪心就好了：

如所有经过的加油站中，多加最便宜的油一定是坠吼的；

这样一来将所有经过的加油站的最大加油量（就是C）和油价加到优先队列里，只要走着走着没油了，就从优先队列取出最便宜的油，加至恰好能到达下一个加油站（因为也许那里的油比你已经经过的更便宜），然后将它的最大加油量减去你加了的部分重新加入队列，如果堆顶的不够加，就继续取第二小，第三小的，如果所有能加的油都加完了还不能到达目的地，就无解。

代码如下，不太好看，勿喷^_^

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct oil{
    double rest,cost;
    bool operator < (const oil& rhs) const{
        return cost>rhs.cost;
    }
};
priority_queue<oil> Q;
double dis[105],cost[105],D1,D2,P,C;
int N;
int main(){
    cin>>D1>>C>>D2>>P>>N;
    dis[0]=0;
    for(int i=1;i<=N;i++){
        cin>>dis[i]>>cost[i];
    }
    dis[N+1]=D1;
    N++;
    for(int i=N;i>=1;i--) dis[i]-=dis[i-1];
    int k=1;
    double ans=0;
    Q.push((oil){C,P});
    while(k<=N){
        double to=dis[k];
        while(to>0){
            if(Q.empty()){
                cout<<"No Solution";
                return 0;
            }
            oil o=Q.top();
            Q.pop();
            if(o.rest*D2>=to){
                o.rest-=to/D2;
                ans+=to/D2*o.cost;
                to=0;
                if(o.rest>0) Q.push((oil){o.rest,o.cost});
            }else{
                to-=o.rest*D2;
                ans+=o.rest*o.cost;
            }
        }
        Q.push((oil){C,cost[k]});
        k++;
    }
    printf("%.2f",ans);
}