汽车加油问题-贪心

问题描述：
　　一辆汽车加满油后可行驶nkm 。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。
编程任务：

　　对于给定的n和k个加油站位置，编程计算最少加油次数。

数据输入：
　　第1行有2个正整数n和k，表示汽车加满油后可行驶nkm，且旅途有k个加油站。接下来的一行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。
结果输出：

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

算法分析：

     假设X[i]表示i-1到i号加油站之间的距离，每一次都是加满油再出发，根据贪心算法的选择性质为了要使加油次数最少就会选择离加满油的点远一点的加油站加油。另外当加满油之后，都要是此后的过程中使加油次数最少。每一次汽车中剩下的油不能再行驶到下一站就在该站加油.每一次加满油之后与起点具有相同的条件，可以看做一个新的起点，过程也是相同的。所以说加油次数最少也具有最优子结构的性质。

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int max_ = 100;
int x[max_];
int len[max_];
int sum = 0;
int flag = 0; // 是否能到达终点
int total;
int n;
int k;
void InPut()
{
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= k + 1; ++i)
    {
        scanf("%d", &len[i]);
    }
}
void GasUp()
{
    total = n;
    for(int i = 1; i <= k + 1; ++i)
        if(total >= len[i])
        {
            total -= len[i];
            if(total > len[i + 1])
                continue;
            else
            {
                total = n;
                x[++sum] = i;
            }
        }
        else
        {
            flag = 1;
            return;
        }
}
void OutPut()
{
    if(flag == 1)
        printf("NO Solution\n");
    else
    {
        printf("最少加油次数为 : %d \n", sum);
        printf("加油站的位置为:\n");
        for(int i = 1; i <= sum; ++i)
            printf("%d ", x[i]);
    }
}
int main()
{
    InPut();
    GasUp();
    OutPut();
}

另外一种方法：

int greedy(vector<int> x,int n)
{
　　int j,i,s,sum=0, k=x.size();
　　for(j=0;j<k;++j)
　　　　if(x[j] > n)　{
　　　　　　cout<<"No Solution"<<endl;
　　　　　　return -1;
　　　　}
　　for(i=0,s=0;i <k; ++i)　{
　　　　s += x[i];
　　　　if(s > n) sum++,s = x[i];
　　}
　　return sum;
}

测试样例：

输入：

7 7

1 2 3 4 5 1 6 6

输出：

最少加油次数为 : 4
加油站的位置为:

3 4 6 7

运行截图：