问题描述

　　一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离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<bits/stdc++.h>
using namespace std;

/*
这就是一个很典型的贪心思路
思路：
从起点开始向后找有没有比当前所在位置的加油站价钱更便宜的加油站
(1)如果有，那么就判断油箱加满能不能到那
    one.如果能到那，那么就从当前的加油点加油使汽车恰好能到比所在加油站便宜且最近的加油点。
    two.如果不能，那么就直接把邮箱加满，去最远能到达的加油站
(2)如果没有，那么直接把油加满，去最远能到达的加油站

以上就是这道题的贪心策略 
*/ 
int main()
{
	double d1,c,d2,p0;
	int n;
 	scanf("%lf %lf %lf %lf %d",&d1,&c,&d2,&p0,&n);
 	
 	double maxl=c*d2;//记录加满油箱最远可行驶的距离 
 	double d[n+2],p[n+2];
 	d[0]=0;//将起点距离记为0 
 	p[0]=p0; 
 	d[n+1]=d1;
 	p[n+1]=0;//将终点的油价记为0 
 	
 	int i,t,j;
 	for(i=1;i<=n;i++)
 	{
 		scanf("%lf %lf",&d[i],&p[i]);
 		if(d[i]-d[i-1]>maxl)//如果有两个点跨度超过最大行驶距离，那么就说明不能到达终点 
 		{
 			printf("No Solution");
 			return 0;
		}
	}  
 	
 	double sum=0,csum=0;
 	int lastp=0;
 	for(i=0;i<=n;i++)
 	{
 	
		if(i!=0)
 		{
			csum-=(d[i]-d[lastp])/d2;
 			if(csum<0)//如果中途邮箱剩余的油小于0，也说明到不了终点 
 			{
 				printf("No Solution");
 				return 0;
			}
		}
	
		int flag=0;
		
		lastp=i;//标记上一次在加油站加油的位置 
		for(t=i+1;t<=n+1;t++)
 		{
 			if(p[t]<p[i]&&t!=n+1)//出现了比当前加油站更便宜的加油点，注意这里判断条件要加上t不是最后一个，因为最后一个加油站的价钱是0，一定比所有的都小 
 			{
 				flag=1;
				if(d[t]-d[i]<=maxl)//能到达那个加油站 
 				{
 					sum+=(d[t]-d[i])/d2*p[i];//加油，使汽车恰好能到达便
 					csum+=(d[t]-d[i])/d2;
 					i=t-1;//更新当前的位置 
 					break;
				}
				else//不能到那个加油站 
				{
					sum+=(c-csum)*p[i];//直接把油箱加满 
					csum=c;
					for(j=t-1;j>i;j--)//找到最远能到达的加油站 
					{
						if(d[j]-d[i]<=maxl)
						{
							i=j-1;
						}
					}
					break;
				}
			}
		}

		if(!flag)//后面没有比当前加油站更便宜的加油站了 
		{
			
			if(d[n+1]-d[i]<maxl)//如果可以直接到终点了，要单独讨论 
			{
				
				sum+=((d[n+1]-d[i])/d2-csum)*p[i];//要扣除已经在邮箱里的油 
				csum=(d[n+1]-d[i])/d2;
				continue;
			}
			sum+=(c-csum)*p[i];
			csum=c;
			for(j=n+1;j>i;j--)//找到最远能到达的加油站 
			{
				if(d[j]-d[i]<=maxl)
				{
					i=j-1;
				}
			}
		}
		
	
	}
 	
 	printf("%.2lf",sum);
 	return 0;
}