汽车加油问题（贪心）

1 问题重述

一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。
Input
输入数据的第一行有2 个正整数n和k（n≤5000，k≤1000），表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有k+1 个整数，表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。

Output
将计算出的最少加油次数输出。如果无法到达目的地，则输出“No Solution!”。

2 算法分析

汽车行驶过程中，应走到自己能走到并且离自己最远的那个加油站，在那个加油站加油后再按照同样的方法贪心，每次汽车中剩下的油不能再行驶到下一个加油站时我们才在这个加油站加一次油，每个过程从加油开始行驶到再次加油满足贪心，且每一次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。

3 算法步骤

1. 输入加满油可行驶公里数和加油站个数；
2. 先检测各加油站之间的距离，若发现其中有一个距离大于汽车加满油能跑的距离，则输出no solution；
3. 否则，对加油站间的距离进行逐个扫描，尽量选择往远处走，不能走了就让count++，最终统计出来的count便是最少的加油站数；
4. 最后，输出加油站加油的位置和最少加油的次数。

4 代码实现

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int i, n, k, a[1010];
    int count = 0;
    cin>>n>>k;
 
    for(i = 0;i<k+1;i++)
    {
        cin>>a[i];
    }
 
    int v = n;
    printf("应在以下加油站加油：");
    for(i = 0;i<k+1;i++)
    {
        if(n<a[i]) break;    
        if(v<a[i])
        {
            count++;
            cout<<i<<" ";
            v = n;
        }
        v-=a[i];
    }
    if(i<k+1) cout<<"No Solution!"<<endl;
    else 
	{
		printf("\n最少加油次数：");
		cout<<count<<endl;	
	}
}

5 运行结果