算法训练 旅行家的预算

  算法训练 旅行家的预算   时间限制：1.0s   内存限制：256.0MB         问题描述 　　一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。 输入格式 　　第一行为4个实数D1、C、D2、P与一个非负整数N；

　　接下来N行，每行两个实数Di、Pi。 输出格式 　　如果可以到达目的地，输出一个实数（四舍五入至小数点后两位），表示最小费用；否则输出“No Solution”（不含引号）。 样例输入 275.6 11.9 27.4 2.8 2

102.0 2.9

220.0 2.2 样例输出 26.95  这个题是经典的贪心算法的题目，自己慢慢终于琢磨出来了，但还是错了几次 自己的代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int main()
{
	double len[100] = {0},price[100],oil_len[100] = {0};
	double d1,c,d2,p,sum = 0;
	int n,flag = 1;
	scanf("%lf %lf %lf %lf %d",&d1,&c,&d2,&p,&n);
	price[0]=p;
	double maxx = d2*c; //表示最多能走的路程 
	for(int i=1;i<=n;i++)
	{
		scanf("%lf %lf",&len[i],&price[i]);
		if(len[i]-len[i-1] > maxx)//判断是否可以到达 
		{
			flag = 0;
		}
	}
	n++;
	len[n] = d1;//不要忽略最后的一段路程 
	if(n == 0&&flag == 1)
	{
		if(c*d2 <= d1)
		{
			printf("%.2lf",d1/d2*p);
		}
		else
		{
			printf("No Solution\n");
		}
	}
	else if(flag == 1)
	{
		int k = 0;
		double temp = 0;
		for(int i = 1;i <= n;i++)
		{
			if(len[i] - temp <= maxx)//此处注意，要用temp标注，本来是想用len【k】的，但是发现如果没油前遇到最后的加油站不便宜的话，要尽量将原来的油用了 ，便宜的油能走多远走多远 
			{
				oil_len[k] = len[i]-temp;
			}
			else
			{
				oil_len[k] = maxx;
				k = i-1;temp += maxx;
				oil_len[k] = len[i] - temp;
			}
		    if(price[i] < p)
			{
				p = price[i];
				k = i;
				temp = len[i];//对已经走过的路程更新 
			}
		}
	}
	if(flag == 0)
	{
		printf("No Solution\n");
	}
	else
	{
		for(int i = 0;i <= n;i++)
		{
			sum += oil_len[i] / d2 * price[i];
		}
		printf("%.2lf",sum);
	}
	return 0;
}
           

  算法训练 旅行家的预算   时间限制：1.0s   内存限制：256.0MB         问题描述 　　一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。 输入格式 　　第一行为4个实数D1、C、D2、P与一个非负整数N；

　　接下来N行，每行两个实数Di、Pi。 输出格式 　　如果可以到达目的地，输出一个实数（四舍五入至小数点后两位），表示最小费用；否则输出“No Solution”（不含引号）。 样例输入 275.6 11.9 27.4 2.8 2

102.0 2.9

220.0 2.2 样例输出 26.95  

•