汽车加油问题

分析

用贪心算法计算加油次数最少就是，计算是否能到下一目的地，不能则加油。（加一次油跑最远的距离）

实现

#include <iostream>
using namespace std;
int main(){
    int n,k,i;	int *station;
    cout<<"请输入加满一箱油的最大行驶路程和加油站的个数：";
    cin>>n>>k;	station=new int[k+1];
    cout<<"请输入相邻的两个加油站之间的距离：";
    for(i=0;i<=k;i++)	cin>>station[i];
    int s=0,number=0;//number记录加油的次数
    s=station[0];//加满油后希望的行驶距离
	for(i=1;i<=k;i++){    //i代表加油站编号 。1~7.代表将要到大的加油站
		if(s>n)	{cout<<“No solutin!!”;	
		                      break;
			          }//判断能否到达i加油站
		else{//能到达加油站i
	  	    s=s+station[i]; //到下一加油i+1站希望的 行使的距离
		   if(s>n){ //希望距离>n 
 		             number++;//加油
		            s=station[i];//到下一加油站的距离
		            cout<<"在第"<<i<<"  个加油站加油"<<endl;
		            }
		       }
	}
	cout<<number<<endl;
	return 0;
   }