1750 汽车加油问题

偏执的太偏执、 2022-02-16 12:43 260阅读 0赞

### 汽车加油问题 ###

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。  
对于给定的n和k个加油站位置，计算最少加油次数。

Input

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

Output

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

Sample Input

7 7
    1 2 3 4 5 1 6 6

Sample Output

4

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int m, n, x, flag =0, rst;
        std::cin >> m >> n;
        rst = m;
        for(int i = 0; i < n+1; i++){
          std::cin >> x;
          if(x > m){            //满油也无法达到
            flag=-1;break;
          }
          else{
              if(rst >= x)    //剩下的油可以到下段路程
                rst -= x;
              else{
                rst = m - x;  //剩下的油不够 需要加油
                flag++;
              }
          }
        }
        if(flag>=0)
          std::cout << flag << '\n';
        else
          std::cout << "No Solution!" << '\n';
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，260人围观）

还没有评论，来说两句吧...

相关阅读

相关虚拟汽车加油问题——算法设计与分析（C实现）

目录一、问题描述二、问题剖析三、代码实现四、结果验证 -------------------- 一、问题描述问题描述：一辆虚拟汽车加满油后

r囧r小猫/ 2024年03月22日 15:07/ 0 赞/ 86 阅读

相关 Java 加油加油加油！！！！！

Java基础 1、三大特性，封装，继承，多态 2、异常 3、多线程 4、集合 5、反射 6、网络 7、IO流 1、三大特性封装理解：私

ゝ一世哀愁。/ 2022年10月22日 10:45/ 0 赞/ 190 阅读

相关算法设计与分析——贪心算法——汽车加油问题

汽车加油问题：一辆汽车加满油后可行驶n公里，旅途中有若干个加油站，两加油站间距离不超n 公里，起点离第一个加油站距离及最后一个加油站离终点距离也不超过n公里。算法给出应在哪些加

雨点打透心脏的1/2处/ 2022年10月15日 12:56/ 0 赞/ 259 阅读

相关汽车加油问题贪心算法c语言,汽车加油问题之贪心算法（全面分析）

一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。给出N，并以数组的形式给出加油站的个数及相

柔光的暖阳◎/ 2022年10月15日 05:55/ 0 赞/ 255 阅读

相关汽车加油问题

汽车加油问题 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述一辆汽车加满油后可行驶

你的名字/ 2022年08月18日 02:30/ 0 赞/ 244 阅读

相关贪心算法之汽车加油问题

场景一、一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。应在哪些加油站停靠加油，使沿途加油次数最少。汽车行驶过程中，不到万不得已不加油，应走到自己能走到并且离自己最远的

短命女/ 2022年07月21日 00:14/ 0 赞/ 280 阅读

相关汽车加油问题(贪心)

汽车加油问题 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Problem

刺骨的言语ヽ痛彻心扉/ 2022年02月23日 12:30/ 0 赞/ 319 阅读

相关 1750 汽车加油问题

汽车加油问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 一辆汽车加满油后可行驶n

偏执的太偏执、/ 2022年02月16日 12:43/ 0 赞/ 261 阅读

相关汽车加油问题

汽车加油问题 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Problem

左手的ㄟ右手/ 2022年02月15日 03:59/ 0 赞/ 295 阅读

相关贪心算法（4）：汽车加油问题

题目一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最算法设计：对于给定的n和k个加油站位置，计算最少加油

电玩女神/ 2022年02月04日 04:15/ 0 赞/ 1228 阅读