汽车加油问题(贪心)

?

问题描述：

　　一辆汽车加满油后可行驶n 公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。

编程任务：

　　对于给定的n 和k 个加油站位置，编程计算最少加油次数。

数据输入：

　　由文件input.txt 给出输入数据。第一行有2 个正整数n 和k，表示汽车加满油后可行驶n 公里，且旅途中有k 个加油站。接下来的1 行中，有k+1 个整数，表示第k 个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。

结果输出:

　　将编程计算出的最少加油次数输出到文件output.txt 。如果无法到达目的地，则输出”No Solution”。

输入文件示例输出文件示例

input.txt?????????????????????? output.txt

7 7????????????????????????????????? 4

1 2 3 4 5 1 6 6

问题的分析利用到了windows自带的"画图"软件:

如下:

具体分析已经在代码中给出了:

#include<iostream>
using namespace std;
const int N=1010;
int f[N];//存储加油站之间的距离 
int n,k,sum,loc,cnt;
int main()
{

	cin>>n>>k;
	
	int waste;
	cin>>waste;//出发点的位置没有用,只需要七个站之间的距离
	//假定出发点为0,简化问题 
	
	for(int i=0;i<k;i++)//k个加油站 
	{
		cin>>f[i];
		sum+=f[i];
	}
	
	int i=-1; 
	while(loc<sum)//loc表示的是当前汽车所在位置,sum表示总里程 
	{
		//d记录的是加油之后最多能走多远 
		int d=0,j=i;
		if(loc+f[j+1]>=sum) break;//如果剩下的油足够走完最后这一段里程,就退出循环 
		while(d<=n)
		{
			d+=f[++j];	
		}	
		d-=f[j];
		j--;//执行完这一步之后,j表示的是加油的站点 
		i=j;//i记录此次加油的站点,方便下次循环使用 
		cnt++;//表示一次加油 
		loc+=d;
		printf("loc=%d,d=%d,j=%d,i=%d,cnt=%d\n",loc,d,j,i,cnt);
	}
	printf("%d",cnt);
	return 0;

}