问题描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=，，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
输入格式
第一行为4个实数D1、C、D2、P与一个非负整数N；
接下来N行，每行两个实数Di、Pi。
输出格式
如果可以到达目的地，输出一个实数（四舍五入至小数点后两位），表示最小费用；否则输出“No Solution”（不含引号）。
样例输入
275.6 11.9 27.4 2.8
102.0 2.9
220.0 2.2
样例输出
26.95
题目描述
代码如下:
#include <stdio.h>
#define MAX 10001 int main(void)
{
int n;
double d1,c,d2,p;
double distance[MAX]; //油站i离出发点的距离Di
double price[MAX]; //各油站的价格Pi
double res = ; //最小费用
double surplus = ; //油箱剩余量
int i,j; scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p,&n); distance[] = ;
distance[n+] = d1; //最后处油站为终点
price[] = p; //出发点油站价格 for (i= ; i<=n ; i++)
{
scanf("%lf%lf",&distance[i],&price[i]);
if (distance[i]-distance[i-] > c*d2) //两油站距离大于汽车最大行驶距离
{
printf("No Solution\n");
return ;
}
}
if (d1-distance[n] > c*d2)
{
printf("No Solution\n");
return ;
} i = ; //油站编号
while (i <= n)//汽车所在油站的位置
{
for (j=i+ ; j<=n+ ; j ++)
{
if (distance[j]-distance[i] < (c-surplus)*d2) //查找最大行驶距离内的较低价油站
{
if (price[j] < price[i]) //找到较低价油站
break;
}
else //当前油站价格最低
{
j --; //记录最大行驶距离内的最远端油站
break;
}
} if (price[j] < price[i])//增加可以刚好抵达j点处油站油量(价格较低)
{
res += ((distance[j]-distance[i])/d2 - surplus)*price[i];
surplus = ;//刚好到达j点处油站，油耗完
}
else //当前位置油价最低，加满油箱
{
res += (c-surplus)*price[i];
surplus = c - (distance[j]-distance[i])/d2;
}
i = j; //汽车行驶到第j个油站/终点
} printf("%.2lf\n",res);
return ;
}
C解法
解题思路:
1.每次输入Di时，判断两油站之间的距离是否大于汽车满油箱时行驶的最大距离，若是则输出"No Solution"
2.开始计算最小费用，每次在汽车满油箱可以行驶的最大距离内，查找是否存在比当前油价低的油站
2.1.找到较低价的油站：往油箱加可以到达较低价油站的油量，并刚好行驶到较低价油站。
2.2.当前油站为最低价：往油箱加满油，并行驶到行程内最远端的油站。
贪心思想：每次在最大行程内，向油箱添加当前情况下的最低价油量，确保最后的费用最少