旅行家的预算

旅行家的预算

题目描述

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

输入

输入五个数，即D1，C，D2，P，N。

接下来共N行，分别表示油站i离出发点的距离Di和每升汽油价格Pi。

输出

输出最小费用。

如无法到达目的地，则输出“No Solution”。

样例输入

275.6 11.9 27.4 2.8 2

102.0 2.9

220.0 2.2

样例输出

26.95

参考代码

/*寻找距离当前站最近的比当前站便宜的站点；
　如果找到了，油量够就直接开过去，油量不够就冲到刚好可以开过去；
　如果找不到，就到前面找一个充满油量能到得了的最便宜的站点，充满油开过去；
　如果加满油找不到任何站点，那就输出No Solution；
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

struct dot{
	double dis, p;
}dots[100001];

double have = 0, used = 0;
double d1, c, d2, p;
int place = 0;

int main() {
	int i, n, id;
	double small;
	scanf("%lf%lf%lf%lf%d", &d1, &c, &d2, &p, &n);
	//两个城市之间的距离d1、汽车油箱的容量c(以升为单位)、每升汽油能行驶的距离d2；
	//出发点每升汽油价格p和沿途油站数n(n可以为零):
	dots[0].p = p;
	dots[n + 1].dis = d1;
	for (i = 1; i <= n; i++) {  //存储路上n个加油站的距离和油价； 
		scanf("%lf%lf", &dots[i].dis, &dots[i].p);
	}
	while (dots[place].dis < d1) {  //在还没到终点的时候； 
		id = -1;
		for (i = place + 1; i <= n + 1; i++) {
			if (dots[place].dis + c * d2 >= dots[i].dis) {  //判断加满油能否驶过下一个路程点； 
				if (dots[i].p <= dots[place].p) {  //再判断下一个路程点的油价是否比前一个便宜； 
					id = i;
					break;
				}
			}
			else {
				break;
			}
		}
		if (i == place + 1 && id == -1) {  //id==-1即没有找到下一个站点；i的值代表已经查找到最后一个站点了； 
			printf("No Solution\n");
			return 0;
		}
		if (id != -1) {  //找到了站点； 
			if(dots[place].dis + have * d2 >= dots[id].dis) {  //油量够就直接开过去； 
				have -= (dots[id].dis - dots[place].dis) / d2;
			}
			else {  //油量不够就冲到刚好可以开过去； 
				used += ((dots[id].dis - dots[place].dis) / d2 - have) * dots[place].p;
				have = 0;
			}
		}
		else {  //如果没有找到站点； 
			small = 100000000;
			id = -1;
			for (i = place + 1; i <= n + 1; i++) {  //就到前面找一个充满油量能到得了的最便宜的站点； 
				if (dots[place].dis + c * d2 >= dots[i].dis) {
					if (small >= dots[i].p) {
						small = dots[i].p;
						id = i;
					}
				}
				else {
					break;
				}
			}
			used += (c - have) * dots[place].p;
			have = c;
			have -= (dots[id].dis - dots[place].dis) / d2;
		}
		place = id;
	}
	printf("%.2lf\n", used);
	return 0;
}