欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

汽车加油问题

程序员文章站 2022-06-08 08:22:04
...

一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法,指出应哪些加油站停靠加油,使沿途加油次数最少。对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置,编程计算最少加油次数。要求:
输入:第一行有2个正整数n和k,表示汽车加满油后可行驶n公里,且旅途中有k个加油站。接下来的1行中,有k+1个整数,表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地,汽车已加满油。第k+1个加油站表示目的地。
输出:输出编程计算出的最少加油次数。如果无法到达目的地,则输出”No Solution”。

汽车加油问题
汽车加油问题

#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;
   }