题解 P1016 【旅行家的预算】
ciyou
2016-11-11 12:17:01
这道题贪心就好了：
> 如所有经过的加油站中，多加最便宜的油一定是坠吼的；
这样一来将所有经过的加油站的最大加油量（就是C）和油价加到优先队列里，只要走着走着没油了，就从优先队列取出最便宜的油，加至恰好能到达下一个加油站（因为也许那里的油比你已经经过的更便宜），然后将它的最大加油量减去你加了的部分重新加入队列，如果堆顶的不够加，就继续取第二小，第三小的，如果所有能加的油都加完了还不能到达目的地，就无解。
代码如下，不太好看，勿喷^\_^
```cpp
#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);
}
```