출발 위치에서 출발 위치에서 동쪽으로 t마일 떨어진 목적지까지 이동하는 자동차가 있다고 가정합니다.
이제 길을 따라 많은 주유소가 있습니다. 따라서 각 스테이션[i]은 시작 위치에서 동쪽으로 스테이션[i][0]마일에 있는 주유소를 나타내며 해당 스테이션에는 주유소[i][1]리터가 있습니다.
자동차가 무한한 크기의 가스 탱크로 시작하는 경우 처음에는 연료 리터의 연료가 들어 있습니다. 주행하는 1마일당 1리터의 가스를 사용합니다.
차가 한 주유소에 도착하면 멈추고 연료를 보급할 수 있으므로 이제 주유소의 모든 주유소를 자동차로 옮깁니다. 차가 목적지에 도달하기 위해 거쳐야 하는 최소 주유 횟수는 얼마인지 찾아야 합니다. 목적지에 도달할 수 없는 경우 -1을 반환합니다.
따라서 입력이 Target =100, startFuel =20, 스테이션 =[10,40],[20,30],[30,20],[60,40]인 경우 출력은 3이 됩니다. 따라서 처음에는 10리터의 가스가 있고 첫 번째 스테이션에 도달한 후 40리터의 가스를 이송하므로 현재 (0 + 40) =40리터 가스가 있고 세 번째 스테이션에 도달하면 이제 20리터의 가스를 이송하므로 현재 수량은 (20+20) =40이고 마지막 스테이션에 도달하고 40리터의 가스를 취하므로 현재 수량(10 + 40) =50입니다. 지금까지 60마일을 이동했으므로 도달하려면 40마일을 더 가야 합니다. 목적지, 목표에 도달하기에 충분한 가스가 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
커 :=0
-
배열 st
정렬 -
우선순위 대기열 pq 정의
-
i :=0, cnt :=0
-
curr :=curr + 연료
-
동안 curr
-
(cnt를 1씩 증가)
-
동안 (i
-
pq에 st[i, 1] 삽입
-
(i를 1씩 증가)
-
-
pq가 비어 있으면 -
-
루프에서 나오세요
-
-
curr :=curr + pq의 최상위 요소
-
pq에서 요소 삭제
-
-
return(curr>=target이면 cnt, 그렇지 않으면 -1)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minRefuelStops(int target, int fuel, vector<vector<int>> &st) {
int curr = 0;
sort(st.begin(), st.end());
priority_queue<int> pq;
int i = 0;
int cnt = 0;
curr += fuel;
while (curr < target) {
cnt++;
while (i < st.size() && st[i][0] <= curr) {
pq.push(st[i][1]);
i++;
}
if (pq.empty())
break;
curr += pq.top();
pq.pop();
}
return curr >= target ? cnt : -1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{10,40},{20,30},{30,20},{60,40}};
cout << (ob.minRefuelStops(100, 10, v));
} 입력
100, 10, {{10,40},{20,30},{30,20},{60,40}} 출력
3