C++贪心算法汽车加油

Question

汽车加油问题，一辆汽车加满油后可以行驶n千米，现需行驶一段具有m千米的旅途，途中有n个加油站，每个加油站的位置是已知的，试问汽车应该在途中哪些加油站停靠加油，以保证顺利到达终点，并且使加油次数最少（重点是需要输入可行驶n，需要行驶m，加油站距离x[]）
C++算法

Answer 1

#include<iostream>
#include<vector>
using namespace std;

bool greeddy(int *distance,int& count,vector<int>& path,int &n,int &m)
{
    //从终点出发，每次走到最远需要加油的位置
    for (int i = n-1; i >= 0; --i)
    {
        //如果两个加油站距离大于n则无解
        if (i!=0&&distance[i] - distance[i - 1] > n)
        {
            return false;
        }
        else if(i==0&&distance[0]>n)
        {
            return false;
        }
        //如果终点到这个加油站的距离大于等于distance[i]，则说明要加油
        if (m - n >= distance[i])
        {
            //大于的时候，应该是在上一个加油站加油
            if (m - n > distance[i])
            {
                i++;
            }
            count++;
            path.push_back(i);
            //此时只用考虑能不能到达这个加油站
            m = distance[i];
            //如果距离小于一次能跑的距离，则可以直接到，不用加油
            if (m <= n)
            {
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int n,m;
    cout << "输入汽车最大行驶距离和加油站数量\n";
    cin >> n;
    cout << "输入行驶目标距离:";
    cin >> m;
    int* distance = new int[n+1];
    cout << "输入加油站距离\n";
    for (int i = 0; i < n; ++i)
    {
        cin >> distance[i];
    }
    if (n >= distance[n - 1])
    {
        cout << "无需加油，直接到达" << endl;
        return 0;
    }
    //路线上添加一个终点的位置
    distance[n] = m;
    int count = 0;
    vector<int> path;
    if (greeddy(distance,count,path,n,m))
    {
        if (!path.size())
        {
            cout << "无需加油";
            return 0;
        }
        cout << "停车加油点:";
    
        for (int i = path.size()-1; i>=0; --i)
        {
            cout << distance[path[i]]<<' ';
        }
        cout << endl;
        cout << "加油总次数：" << count << endl;
    }
    else
    {
        cout << "不可达";
    }
}

提供几组参考数据
n=5 m=5, 加油站坐标1 2 3 4 5
n=5 m=25 加油站坐标 5 10 15 20 25
n=5 m=12 加油站坐标1 2 7 8 9
n=5 m=12 加油站坐标1 2 6 8 9