80621 2022-05-20 23:00 采纳率: 100%
浏览 202
已结题

C++贪心算法汽车加油

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

  • 写回答

3条回答 默认 最新

  • 下坠丷 2022-05-21 01:24
    关注
    
    #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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 5月29日
  • 已采纳回答 5月21日
  • 创建了问题 5月20日

悬赏问题

  • ¥20 管道轴向耦合水击问题
  • ¥60 补全networkx TODO部分。
  • ¥15 有内推吗,云计算linux运维方向
  • ¥30 sort cuteSV.vcf by bcftools用IGV可视化出现报错
  • ¥100 SOS!对STK中导出的天体图像进行质心提取有没有人做过啊
  • ¥15 python 欧式距离
  • ¥15 运行qteasy报错
  • ¥15 遗传算法解决有工序顺序约束的大规模FJSP问题
  • ¥15 企业消防水炮塔设计方案
  • ¥20 WORKBENCH网格划分