[文章目录]
Description
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离d1、汽车油箱的容量c（以升为单位）、每升汽油能行驶的距离d2、出发点每升汽油价格p和沿途油站数n，油站i离出发点的距离d[i]、每升汽油价格p[i]。 计算结果四舍五入至小数点后两位。 如果无法到达目的地，则输出-1。（n<=100）
说实话，如果再出这道题，我很可能被一个零基础的小朋友秒杀掉。。。
没有用到任何的数据结构还有算法。
对于每一个加油站，我们看他后面能走到的加油站，如果有更便宜的加油站，那么只需要加足油使自己能够到达那个加油站即可。如果没有，加满，继续走下一个加油站，看是否需要再加一些油。用一个now存储当前的位置，加ans时判断一下是否已经加够到该地的油（也就是说买完了那些油）。
理论上的确是水题，但是，蒟蒻表示做不到啊。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
double c,v,now,ans;
int n;
struct node
{
double dis,p;
}a[110];
bool cmp(node x,node y)
{
return x.dis<y.dis;
}
int main()
{
scanf("%lf%lf%lf%lf%d",&a[2].dis,&c,&v,&a[1].p,&n);
a[2].p=0;a[1].dis=0;n+=2;
for(int i=3;i<=n;i++)
scanf("%lf%lf",&a[i].dis,&a[i].p);
sort(a+1,a+n+1,cmp);
int k=1;
double mxx=v*c;
while(k<=n)
{
if(a[k+1].dis-a[k].dis>mxx) {cout<<"-1";return 0;}
int j=k+1;
while(j<=n&&a[j].dis-a[k].dis<mxx)
{
ans+=a[k].p*max(a[j].dis-now,0.0)/v;now=max(now,a[j].dis);
if(a[j].p<a[k].p){k=j;break;}
else j++;
}
if(k!=j) ans+=a[k].p*(min(a[k].dis+mxx,a[n].dis)-now)/v,now=min(a[n].dis,a[k].dis+mxx),k++;
}
printf("%.2lf\n",ans);
return 0;
}