/
//一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效 //
//
// n和k个加油站位置，编程计算最少加油次数。并证明算法能产生一个最优解。 //
//要求： //
//输入：第一行有个正整数n和k，表示汽车加满油后可行驶n公里， //
//且旅途中有k个加油站。接下来的行中，有k+1个整数，表示第k个加 //
//油站与第k-1个加油站之间的距离。第个加油站表示出发地，汽车已加 //
//满油。第k+1个加油站表示目的地。 //
//输出：输出编程计算出的最少加油次数。如果无法到达目的地，//
//则输出”NoSolution”。 //
//思路： //
//汽车行驶过程中，应走到自己能走到并且离自己最远的那个加油站， //
//在那个加油站加油后再按照同样的 //
/
/
//TITLE:贪心算法汽车加油问题 //
//EDITOR:小桥流水 //
//DADE：.12.7 //
//TOOL:Microsoft Visual Studio //
/
//METHOD: 用向量实现 //
/
#include"stdafx.h"
#include
#include
#include
usingnamespacestd;
void_tmain(intargc,_TCHAR*argv[])
{
vectorv;
vectorv1;
intn,k,i,sum=0,count=0;
boolisSolution=true;
ifstreamfin;
fin.open("input.txt");//打开文件
fin>>n>>k;//从文件中读取汽车加满油后可行驶距离n，加油站的个数k
inttemp;
for(i= 0;i<=k;i++)//循环的从文件中读取各加油站的间距
{
fin>>temp;
v.push_back(temp);
}
i= 0;
ofstreamfout("output.txt");
while(i<=k)
{
if(v[i]>n)//如果成立，则不能到达目的地
{
isSolution=false;
break;//跳出循环
}
count+=v[i];
if(count>n)
{
v1.push_back(i);//记录最优解
count= 0;
sum++;//m记录最少的加油次数
}
else
{
i+= 1;
}
}
if(isSolution)//将结果写入文件
fout<
else
fout<
cout<
cout<
for(i= 0;i
{
cout<
}
cout<
fout.close();//关闭文件
fin.close();
}
/
//METHOD: 用指针实现 //
/
#include"stdafx.h"
#include
#include
usingnamespacestd;
voidmain()
{
int*a,*b,n,k,i,m=0,count=0;
boolisSolution=true;
ifstreamfin;
fin.open("input.txt");//打开文件
fin>>n>>k;//从文件中读取汽车加满油后可行驶距离n，加油站的个数k
a=newint[k+1];
for(i= 0;i<=k;i++)//循环的从文件中读取各加油站的间距
fin>>a[i];
b=newint[k+1];
b[0] = 0;
i= 0;
ofstreamfout("output.txt");
