C++ log 2k 2017春算实验 1

贪心算法解决汽车加油问题

描述

一辆汽车在油箱加满后能够行驶n公里。在旅途中存在多个加油站。设计一个高效的算法，确定应在哪些加油站进行加油操作，以使得整个行程中加油的次数最少。

输入

第一行包含2个正整数n和k，分别表示汽车加满油后可行驶的距离以及旅途中的加油站数量。接下来的一行包含k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。其中，第0个加油站为出发点，汽车已加满油；而第k+1个加油站为目的地。

输出

输出计算得到的最少加油次数。若无法抵达目的地，则输出”No Solution”。

示例输入

7 7
1 2 3 4 5 1 6 6

示例输出

4

asw:

    #include<stdio.h>
    int a[100];
    int count=0;
    void Count(int n,int k)
    {
    int i,j,flag=0;
    for(i=0;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]>n)      //判断加油站间距离超过满油走的一趟路程长度
            flag=1;
        }
    if(flag==1){
        printf("No S