当前位置:网站首页>LeetCode 871. 最低加油次数
LeetCode 871. 最低加油次数
2022-07-04 18:53:00 【JIeJaitt】
汽车从起点出发驶向目的地,该目的地位于出发位置东面 target
英里处。
沿途有加油站,每个 station[i]
代表一个加油站,它位于出发位置东面 station[i][0]
英里处,并且有 station[i][1]
升汽油。
假设汽车油箱的容量是无限的,其中最初有 startFuel
升燃料。它每行驶 1 英里就会用掉 1 升汽油。
当汽车到达加油站时,它可能停下来加油,将所有汽油从加油站转移到汽车中。
为了到达目的地,汽车所必要的最低加油次数是多少?如果无法到达目的地,则返回 -1
。
注意:如果汽车到达加油站时剩余燃料为 0,它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0,仍然认为它已经到达目的地。
示例 1:
输入:target = 1, startFuel = 1, stations = [] 输出:0 解释:我们可以在不加油的情况下到达目的地。
示例 2:
输入:target = 100, startFuel = 1, stations = [[10,100]] 输出:-1 解释:我们无法抵达目的地,甚至无法到达第一个加油站。
示例 3:
输入:target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]] 输出:2 解释: 我们出发时有 10 升燃料。 我们开车来到距起点 10 英里处的加油站,消耗 10 升燃料。将汽油从 0 升加到 60 升。 然后,我们从 10 英里处的加油站开到 60 英里处的加油站(消耗 50 升燃料), 并将汽油从 10 升加到 50 升。然后我们开车抵达目的地。 我们沿途在1两个加油站停靠,所以返回 2 。
提示:
1 <= target, startFuel, stations[i][1] <= 10^9
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target
贪心题,证明起来比较困难,但是思路比较直接。
具体做法如下。
计算当前位置(加油站或目的地)与上一个位置的距离之差,根据该距离之差得到从上一个位置行驶到当前位置需要使用的汽油量,将使用的汽油量从剩余的汽油量中减去。
如果剩余的汽油量小于 000,则表示在不加油的情况下无法从上一个位置行驶到当前位置,需要加油。取出优先队列中的最大元素加到剩余的汽油量,并将加油次数加 111,重复该操作直到剩余的汽油量大于等于 000 或优先队列变为空。
如果优先队列变为空时,剩余的汽油量仍小于 000,则表示在所有经过的加油站加油之后仍然无法到达当前位置,返回 −1-1−1。
如果当前位置是加油站,则将当前加油站的加油量添加到优先队列中,并使用当前位置更新上一个位置。
class Solution {
public:
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
stations.push_back({
target,0});
int res=0;
priority_queue<int> heap;
for (auto& p:stations) {
int x=p[0],y=p[1];
while(heap.size() && startFuel<x) {
startFuel += heap.top();
heap.pop();
res ++;
}
if (startFuel<x) return -1;
heap.push(y);
}
return res;
}
};
边栏推荐
- Write it down once Net analysis of thread burst height of an industrial control data acquisition platform
- Lingyun going to sea | Murong Technology & Huawei cloud: creating a model of financial SaaS solutions in Africa
- 哈希(Hash)竞猜游戏系统开发功能分析及源码
- 输入的查询SQL语句,是如何执行的?
- Taishan Office Technology Lecture: about the order of background (shading and highlighting)
- Selected review | machine learning technology for Cataract Classification / classification
- Is it safe for Great Wall Securities to open an account? Stock account opening process online account opening
- c# . Net MVC uses Baidu ueditor rich text box to upload files (pictures, videos, etc.)
- Optimize if code with policy mode [policy mode]
- Aiming at the "amnesia" of deep learning, scientists proposed that based on similarity weighted interleaved learning, they can board PNAS
猜你喜欢
Actual combat simulation │ JWT login authentication
上线首月,这家露营地游客好评率高达99.9%!他是怎么做到的?
Application practice | Shuhai supply chain construction of data center based on Apache Doris
Employment prospects and current situation of Internet of things application technology
Related concepts of federal learning and motivation (1)
Pytoch learning (4)
紫光展锐完成全球首个 5G R17 IoT NTN 卫星物联网上星实测
Actual combat simulation │ JWT login authentication
Flet教程之 06 TextButton基础入门(教程含源码)
So this is the BGP agreement
随机推荐
#夏日挑战赛#带你玩转HarmonyOS多端钢琴演奏
凌云出海记 | 一零跃动&华为云:共助非洲普惠金融服务
What should we pay attention to when doing social media marketing? Here is the success secret of shopline sellers!
长城证券开户安全吗 股票开户流程网上开户
@Data source connection pool exhaustion caused by transactional abuse
What are the consequences of closing the read / write channel?
Multi table operation inner join query
Actual combat simulation │ JWT login authentication
Optimization cases of complex factor calculation: deep imbalance, buying and selling pressure index, volatility calculation
What is the application technology of neural network and Internet of things
Actual combat simulation │ JWT login authentication
Crystal optoelectronics: ar-hud products of Chang'an dark blue sl03 are supplied by the company
Lingyun going to sea | Wenhua online & Huawei cloud: creating a new solution for smart teaching in Africa
YOLOv5s-ShuffleNetV2
ACM组合计数入门
实战模拟│JWT 登录认证
Integretee integrates into Moonriver through xcm, bringing enterprise class privacy solutions to its ecosystem
C language - Introduction - Foundation - grammar - process control (VII)
Oracle database, numbers Force 2 decimal places to display-Alibaba Cloud
记一次 .NET 某工控数据采集平台 线程数 爆高分析