汽车加油问题
程序员文章站
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;
}
上一篇: 模板引擎正则表达式调试小技巧_PHP
下一篇: 正则全局匹配模式g修饰符的使用详解