旅行家的预算

题目描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离D1、汽车油箱的容量C(以升为单位)、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N(N可以为零)，油站i离出发点的距离Di、每升汽油价格Pi(i＝1，2，…，N)。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。

输入

第一行有四个数，分别表示D1，C，D2，P，N
接下来有N行，每行2个数，分别表示油站i离出发点的距离Di和每升汽油价格Pi

输出

最小费用

样例输入

275.6  11.9  27.4  2.8  2
102.0  2.9 
220.0  2.2

样例输出

26.95

#include <bits/stdc++.h>
using namespace std;
#define precision 0.00001
struct node
{
double dd,pp;
}s[100000];
bool cmp(node a,node b){return a.dd<b.dd;}
double d1,c,d2,p;
int n;
int main(){
//ios::sync_with_stdio(false);
int i,j,k;
double f,ans,x,y;
    cin>>d1>>c>>d2>>p>>n;
    s[1].dd=0,s[1].pp=p;
    s[2].dd=d1,s[2].pp=0;
for(n+=2,i=3;i<=n;i++) cin>>s[i].dd>>s[i].pp;
    sort(s+1,s+n+1,cmp);
    k=1,ans=x=0,f=c*d2;
while(k<=n)
    {
if(s[k+1].dd-s[k].dd>f) {cout<<"No Solution"<<endl;return 0;}//当路程大于加满油后的最大路程；
for(j=k+1;s[j].dd-s[k].dd<=f&&j<=n;j++){//在该油站找遍历可以直接到达的下一个油站
if(s[j].pp<=s[k].pp){//找到比该油站便宜的油
               y=(s[j].dd-s[k].dd)/d2;//到达那个油站需要在该油站充多少
if(x<y) ans+=s[k].pp*(y-x),x=0;//到达那个便宜油站后剩余量x=0
else x-=y;
               k=j;//跳过中间油站
break;
            }
        }
if(fabs(s[k].dd-d1)<=precision){//到达目的地
                printf("%.2lf\n",ans);
return 0;
            }
if(j!=k){//找不到合适的 说明本油站是最佳 就在本油站加满油
                ans+=s[k].pp*(c-x);
                x=c-(s[k+1].dd-s[k].dd)/d2;//到下一个油站需要的油
                k++;
            }
    }
return 0;
}

要么找不到合适的在本油站加满，要么找到油花费少的，花费至少到达那个油站的油。