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

电玩女神 2022-02-04 04:15 1207阅读 0赞

## 题目 ##

一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最算法设计：对于给定的n和k个加油站位置，计算最少加油次数据输入：n：表示汽车加满油后可行驶nkm k：旅途中有k个加油站 k+1个整数：表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地  
输入加满油行驶的距离n,和加油站的个数  
数据输出：最少加油次数和具体在哪几个加油站加油。  
注意,加上起点和终点一共k+2-1个间隔

## 样例 ##

输入  
7 7  
1 2 3 4 5 1 6 6  
输出  
4

## 题解 ##

每次都想着走到快没油了再加油,所以每到一个加油站判断当前的油可不可以走完到下一个加油站的位置,能就不加,不能就加,其中如果加满了油都走不到下一个加油站就输出no solution

## c++代码 ##

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define N 100
    int main(){ 
    	int stations[N];//间距
    	int ins; //加满最多走多远
    	int num;//中间的加油站数
    	int lv;	//当前的油可以走多远
    	scanf("%d%d",&ins,&num);
    	lv=ins;	
    	for(int i=0;i<num+1;i++)
    	{ 
    		 scanf("%d",&stations[i]);
    	}
    	int all=0;
    	for(int i=0;i<num+1;i++)
    	{ 
    		if(stations[i]>ins) 
    		{ 
    	     	printf("No Solution");
    	    	return 0;
    		}
    		if(lv>=stations[i])
    		{ 
    			lv-=stations[i];
    		}
    		else
    		{  
    			lv=ins-stations[i];
    			all++;
    		}
    	}
    	printf("%d\n",all);
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

相关汽车加油问题

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

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

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

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

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

相关算法4.贪心算法的调度问题。

1. ![这里写图片描述][SouthEast] A = \{1, 2, 3, 4, 5\} T = \{5, 8, 4, 10, 3\}

r囧r小猫/ 2022年07月14日 13:42/ 0 赞/ 179 阅读

相关贪心算法4：删数问题

题目描述键盘输入一个高精度的正整数N，去掉其中任意kk个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和k，寻找一种方案使得剩下的数字组成的新数最小。

怼烎@/ 2022年05月07日 04:58/ 0 赞/ 419 阅读

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

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

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

相关 1750 汽车加油问题

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

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

相关汽车加油问题

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

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

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

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

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