当前位置:网站首页>871. 最低加油次数
871. 最低加油次数
2022-07-02 14:21:00 【anieoo】
原题链接:871. 最低加油次数
solution:
本题考察优先队列+贪心。题目的意思是相当于在行驶的过程中把途径的汽油全部携带在身上,如果汽车无法抵达下一个加油站则把汽油最多的那个油桶加上,最后统计加油的次数。
class Solution {
public:
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
if(stations.size() == 0) { //没有加油站,能否抵达只取决于初始油量
if(startFuel >= target) return 0;
else return -1;
}
priority_queue<int,vector<int>,less<int>> heap; //定义大根堆
int miles = startFuel; //可以抵达的距离
int res = 0;//加油次数
for(int i = 0;i < stations.size();i++) {
if(miles >= target) return res; //可以抵达跳出循环
while(miles < stations[i][0]) { //当公里数不够抵达下一个加油站的时候
if(heap.empty()) return -1; //没有汽油可加,不能抵达
auto oil = heap.top();
heap.pop();
miles += oil;
res++;
}
heap.push(stations[i][1]);
}
//已经携带了全部的汽油,但还没抵达终点进行特判
while(miles < target) {
if(heap.empty()) return -1;
auto oil = heap.top();
heap.pop();
miles += oil;
res++;
}
return res;
}
};
边栏推荐
- PhD Debate-11 预告 | 回顾与展望神经网络的后门攻击与防御
- LeetCode 6. Zigzag transformation (n-shaped transformation)
- pwm呼吸灯
- AP and F107 data sources and processing
- PWM breathing lamp
- Leetcode1380: lucky numbers in matrix
- What is the difference between JSP and servlet?
- Executive engine module of high performance data warehouse practice based on Impala
- 【Leetcode】13. Roman numeral to integer
- 亚马逊云科技 Community Builder 申请窗口开启
猜你喜欢
AP and F107 data sources and processing
Interview summary of large factories
配置基于接口的ARP表项限制和端口安全(限制用户私自接入傻瓜交换机或非法主机接入)
你想要的宏基因组-微生物组知识全在这(2022.7)
Machine learning perceptron model
【云原生】简单谈谈海量数据采集组件Flume的理解
go-zero微服务实战系列(八、如何处理每秒上万次的下单请求)
【Leetcode】14. Longest Common Prefix
[North Asia data recovery] data recovery case of raid crash caused by hard disk disconnection during data synchronization of hot spare disk of RAID5 disk array
Seal Library - installation and introduction
随机推荐
深度学习图像数据自动标注[通俗易懂]
TCP server communication process (important)
VMware install win10 image
C语言中sprintf()函数的用法
二、mock平台的扩展
[essay solicitation activity] Dear developer, RT thread community calls you to contribute
社交元宇宙平台Soul冲刺港股:年营收12.8亿 腾讯是股东
使用知行之桥的API端口,提供资源供合作伙伴访问
linux安装postgresql + patroni 集群问题
易语言abcd排序
[cloud native] briefly talk about the understanding of flume, a massive data collection component
LeetCode 4. Find the median (hard) of two positive arrays
Global and Chinese markets for slotting milling machines 2022-2028: Research Report on technology, participants, trends, market size and share
pwm呼吸燈
Tech talk activity preview | building intelligent visual products based on Amazon kVs
Leetcode1380: lucky numbers in matrix
System Verilog implements priority arbiter
LeetCode 6. Zigzag transformation (n-shaped transformation)
如何与博格华纳BorgWarner通过EDI传输业务数据?
Global and Chinese markets for disposable insulin pumps 2022-2028: Research Report on technology, participants, trends, market size and share