1차선 도로를 따라 같은 목적지로 가는 N 대의 자동차가 있다고 가정합니다. 목적지는 '목표' 마일 떨어져 있습니다. 이제 각 자동차 i는 일정한 속도 값 속도[i](시간당 마일)를 가지며 초기 위치는 도로를 따라 목표물을 향한 위치[i]마일입니다.
차는 앞의 다른 차를 절대 추월할 수 없지만 같은 속도로 앞범퍼를 따라잡을 수 있습니다. 여기에서 이 두 자동차 사이의 거리는 무시됩니다. 두 자동차는 같은 위치에 있다고 가정합니다. 자동차 함대는 동일한 위치와 속도로 주행하는 비어 있지 않은 자동차 세트입니다. 한 대의 차량이 목적지 지점에서 차량 함대를 따라잡더라도 여전히 한 대의 차량으로 간주됩니다. 따라서 목적지에 도착할 차량 수를 찾아야 합니다.
따라서 목표가 12이고 위치가 [10,8,0,5,3]이고 속도가 [2,4,1,1,3]이면 출력은 3이 됩니다. 이는 자동차가 10에서 시작하기 때문입니다. 그리고 8은 플릿이 되어 12시에 서로 만납니다. 이제 0에서 시작하는 차는 다른 차를 따라가지 못하므로 그 자체로 플릿입니다. 다시 5시와 3시에 출발하는 차량은 함대가 되어 6시에 서로를 만납니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 배열 v, n :=위치 배열 p의 크기
- 0 ~ n – 1 범위의 i에 대해
- v에 (p[i], s[i]) 삽입
- ret :=n
- v 배열 정렬
- 스택 st 정의
- 0 ~ n – 1 범위의 i에 대해
- temp :=(t – v[i]의 첫 번째 요소) / v[i]의 두 번째 요소
- st가 비어 있지 않고 스택 상단 <=temp
- ret 1 감소
- st에서 최상위 요소 삭제
- st에 온도 삽입
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int carFleet(int t, vector<int>& p, vector<int>& s) {
vector < pair <double, double> > v;
int n = p.size();
for(int i = 0; i < n; i++){
v.push_back({p[i], s[i]});
}
int ret = n;
sort(v.begin(), v.end());
stack <double> st;
for(int i = 0; i < n; i++){
double temp = (t - v[i].first) / v[i].second;
while(!st.empty() && st.top() <= temp){
ret--;
st.pop();
}
st.push(temp);
}
return ret;
}
};
main(){
vector<int> v1 = {10, 8, 0, 5, 3};
vector<int> v2 = {2,4,1,1,3};
Solution ob;
cout << (ob.carFleet(12, v1, v2));
} 입력
12 [10,8,0,5,3] [2,4,1,1,3]
출력
3