1952 - 汽车加油问题
一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。
【设计任务】
对于给定的n和k个加油站位置，计算最少加油次数
题目输入
第一行有2个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。
题目输出
将计算出的最少加油次数输出。如果无法到达目的地，则输出”No Solution”。
输入/输出样例
题目输入
7 7 1 2 3 4 5 1 6 6
题目输出
4
提示
把两加油站的距离放在数组中，a[1..n]表示从起始位置开始跑，经过n个加油站，a[k]表示第k－1个加油站到第k个加油站的距离。汽车在运行的过程中如果能跑到下一个站则不加油，否则要加油。
<span style="color:#555555;background-color:#ffffff;"></span>
C语言解答
#include <stdio.h> int main() { int a[100]; int n,N,cout=0; int i,sum=0; scanf("%d%d",&n,&N); for(i=0;i<=n;i++) { scanf("%d",&a[i]); } for(i=0;i<=n;i++) if(a[i]>N) printf("No Solution"); for(i=0;i<=n;i++) { sum+=a[i]; if(sum>N) { sum=0; i=i-1; cout++; } } printf("%d\n",cout); return 0; }
C++解答
#include<iostream> using namespace std; int static b[1000]; int static N; void check(int c[1000],int g){ int k=N; int sum=0; for(int p=1;p<=g;p++){ if(c[p]>=k){ k=k+N-c[p]; sum+=1; } else k=k-c[p]; } cout<<sum; } int main(){ int a[1000],i=1;int j; cin>>N; cin>>j; while(cin>>a[i]&&i<=j){ i++; } check(a,i); }
提示
把两加油站的距离放在数组中，a[1..n]表示从起始位置开始跑，经过n个加油站，a[k]表示第k－1个加油站到第k个加油站的距离。汽车在运行的过程中如果能跑到下一个站则不加油，否则要加油。
<span style="color:#555555;background-color:#ffffff;"></span>