算法设计与分析_3_25---汽车加油问题（贪心算法-简）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法设计与分析_3_25---汽车加油问题（贪心算法-简），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1115字，纯文字阅读大概需要2分钟。

内容图文

 

【问题描述】试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站，试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。

编程任务：

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

数据输入：

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

结果输出：

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

测试样例：

输入：

7 7

1 2 3 4 5 1 6 6

输出：

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

3 4 6 7

#include <iostream>
#include <stdlib.h>
using namespace std;

void oil(int n,int k,int d[],int m[])
{
    int num=0;
    for(int i=0;i<=k;i++)
    {
        if(d[i]>n)
        {
            cout<<"No Solution"<<endl;
            return;
        }
    }
    int c=0;
    for(int i=0,s=0;i<=k;i++)
    {
        s=s+d[i];
        if(s>n)
        {
            num++;
            s=d[i];
            m[c]=i;
            c++;
        }
    }
    cout<<"最少的加油站数为："<<num<<endl;
    cout<<"加油站的位置为:"<<endl;
    for(int i=0;i<c;i++)
    {
        cout<<m[i]<<" ";
    }
}

int main()
{
    int n,k;
    int d[1000];
    int *m=(int*)calloc(k,sizeof(int));
    cin>>n>>k;
    for(int i=0;i<=k;i++)
    {
        cin>>d[i];
    }
    oil(n,k,d,m);
}

 

内容总结

以上是互联网集市为您收集整理的算法设计与分析_3_25---汽车加油问题（贪心算法-简）全部内容，希望文章能够帮你解决算法设计与分析_3_25---汽车加油问题（贪心算法-简）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---