题解 P1016 【旅行家的预算】
贪心 AC
------------（利用了简单的队列存要走的油站）
好不容易AC了翻翻评论区，决心认认真真哒写个题解造福和自己一样的小可爱们
注释写的炒鸡清楚啦QAQ！蒟蒻在第四个点上卡了1hour
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
double all,each,c,full;
double dis[10],price[10],cost,oil,add,need;
int n,tmp,now;
queue<int>q; //用队列表示走过的油站
int main(){
scanf("%lf%lf%lf%lf%d",&all,&c,&each,&price[0],&n); //读入
tmp=0,full=each*c; //full表示单次最大行驶距离
dis[n+1]=all; //存入到达终点用的距离
price[n+1]=99999999; //将到达终点的价格初始化为最大值（用于之后进行比较）
for(int i=1;i<=n;i++) scanf("%lf%lf",&dis[i],&price[i]); //读入
for(int i=1;i<=n+1;i++){
if(dis[i]-dis[i-1]>full){ //如果两油站间距离超过最大到达距离，结束程序
printf("No Solution");
return 0;
}
if(price[i]<price[tmp]&&dis[i]-dis[tmp]<=full){ //如果该油站油费<当前位置油站的油费，且能够抵达，加入队列
q.push(i);
tmp=i; //更新当前油站的位置
}
else if(dis[i]-dis[tmp]>full){ //如果该油站距离>最大行驶距离
q.push(i-1); //将前一个油站加入队列
tmp=i-1; // 将当前油站的位置更新为前一个油站
i--; //重新比较当前油站
}
}
q.push(n+1); //将终点加入队列
price[n+1]=0; //因为比较结束，将终点油费更改为0
while(q.size()){
int x=q.front(); //x表示要到达的油站
q.pop();
if(price[x]>price[now]){ //如果要到达的油站油费>当前油站油费
add=c-oil; //加满油
oil=c-(dis[x]-dis[now])/each; //更改油量
cost+=add*price[now]; //记录费用
}
else{ // 如果要到达的油站油费<=当前油站油费
need=(dis[x]-dis[now])/each; // need表示需要的油量
if(oil>=need) oil-=need; //如果当前油量大于需要的，不加油
else{ // 如果当前油量不够，加刚好到达下一站的油
add=need-oil;
oil+=add-need; //更改油量
cost+=add*price[now]; //记录费用
}
}
now=x; //更改当前油站位置
}
printf("%.2lf",cost); //输出
}