4-9 汽车加油问题（贪心算法）_汽车加油问题，算法

• 问题描述：一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应
  在哪些加油站停靠加油，使沿途加油次数最少。对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置，编程计算最少加油次数。并证明算法能产生一个最优解。
• 算法设计：对于给定的n和k个加油站的位置，计算最少的加油次数。
• 数据输入：第一行有两个正整数n和k，表示汽车加油后可行驶n km，且旅途中有k个加油站。接下来的一行中，有k+1个整数，表示第k个加油站和第k-1个加油站之间的距离。
• 结果输出：将计算的最少加油次数输出，如果无法到达目的地，则输出“No Solution”。

/*4-9汽车加油问题*/
# include <iostream>
# include <malloc.h>
using namespace std;

void F(int *d, int n, int k)
{
    int num=0;             //Record the times of refueling(加油)
    for (int i=0; i<=k; ++i)
        if (d[i]>n)
        {
            cout <<"No Solution"<<endl;
            return;
        }
    for (int i=0, s=0; i<=k; ++i)
    {
        s+=d[i];
        if (s>n)
        {
            num++;
            s=d[i];
        }
    }
    cout <<num<<endl;
}

int main()
{
    int n, k, *d;
    cin >>n>>k;
    d=(int *)malloc((k+1)*sizeof(int));
    for (int i=0; i<=k; ++i)
        cin >>d[i];
    F(d, n, k);
    return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36