题目描述 Description
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
输入描述 Input Description
第一行D1 C D2 P N
之后N行，每行2个数表示离出发点的距离Di和每升汽油的价格Pi
输出描述 Output Description
最消费用，保留2位小数
样例输入 Sample Input
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
样例输出 Sample Output
26.95
数据范围及提示 Data Size & Hint
N<=100
题解
贪心，怪怪的。
寻找距离当前站最近的比当前站便宜的站点：
1、如果找到了，油量够就直接开过去，油量不够就加到满可以开过去
2、如果找不到，就到前面找一个充满油量后能到达的最便宜的站点，充满油开过去。
3、如果加满油找不到任何站点，那就输出No Solution。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
double len,m,v;
int n;
struct zhan{double dis,c;} a[102];
void init()
{
scanf("%lf%lf%lf%lf%d",&len,&m,&v,&a[0].c,&n);
int i;
for(i=1;i<=n;i++)
scanf("%lf%lf",&a[i].dis,&a[i].c);
a[n+1].dis=len;
}
void work()
{
int i,p=0,to;
double cost=0,rest=0,minc;
while(a[p].dis<len)
{to=-1;
for(i=p+1;i<=n+1;i++)
{if(a[p].dis+m*v<a[i].dis) break;
else
{if(a[i].c<=a[p].c) {to=i; break;}}
}
if(i==p+1&&to==-1) {printf("No Solution\n"); return;}
if(to!=-1)
{if(rest*v+a[p].dis>=a[to].dis)
rest-=(a[to].dis-a[p].dis)/v;
else
{cost+=((a[to].dis-a[p].dis)/v-rest)*a[p].c;
rest=0;
}
}
else
{to=-1; minc=1e15;
for(i=p+1;i<=n+1;i++)
{if(a[p].dis+m*v<a[i].dis) break;
else
{if(a[i].c<=minc) {to=i; minc=a[i].c;}
}
}
cost+=(m-rest)*a[p].c;
rest=m; rest-=(a[to].dis-a[p].dis)/v;
}
p=to;
}
printf("%.2lf\n",cost);
}
int main()
{
init(); work();
return 0;
}