สมมติว่ามีรถ N คันที่ไปยังจุดหมายเดียวกันตามถนนเลนเดียว ปลายทางคือ 'เป้าหมาย' ห่างออกไป ตอนนี้รถแต่ละคันมีค่าความเร็วคงที่ speed[i] (เป็นไมล์ต่อชั่วโมง) และตำแหน่งเริ่มต้นคือตำแหน่ง [i] ไมล์ไปยังเป้าหมายตลอดเส้นทาง
รถไม่สามารถแซงรถคันอื่นข้างหน้าได้ แต่สามารถไล่ตามและขับกันชนไปที่กันชนด้วยความเร็วเท่ากัน ที่นี่ระยะห่างระหว่างรถสองคันนี้ถูกละเว้น - ถือว่ามีตำแหน่งเดียวกัน กองรถคือรถบางส่วนที่ไม่ว่างซึ่งขับอยู่ในตำแหน่งเดียวกันและด้วยความเร็วเท่ากัน หากรถยนต์คันหนึ่งถึงขบวนรถที่จุดปลายทาง จะยังถือว่าเป็นกองรถยนต์หนึ่งคัน เลยต้องหาจำนวนรถที่จะถึงที่หมาย
ดังนั้นหากเป้าหมายคือ 12 หากตำแหน่งคือ [10,8,0,5,3] และความเร็ว [2,4,1,1,3] ผลลัพธ์จะเป็น 3 เนื่องจากรถยนต์เริ่มต้นที่ 10 และ 8 กลายเป็นกองเรือพบกันตอน 12 โมง ตอนนี้รถที่เริ่มต้นที่ 0 นั้นไม่สามารถตามรถคันอื่นได้ดังนั้นจึงเป็นฝูงบินด้วยตัวมันเอง อีกครั้งที่รถที่เริ่มต้นที่ 5 และ 3 กลายเป็นกองเรือพบกันที่ 6
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างอาร์เรย์ v, n :=ขนาดของตำแหน่งอาร์เรย์ p
- สำหรับ i ในช่วง 0 ถึง n – 1
- แทรก (p[i], s[i]) ลงใน v
- ret :=n
- จัดเรียง v อาร์เรย์
- กำหนดสแต็ก st
- สำหรับ i ในช่วง 0 ถึง n – 1
- temp :=(t – องค์ประกอบแรกของ v[i]) / องค์ประกอบที่สองของ v[i]
- ในขณะที่ st ไม่ว่างและ stack top <=temp
- ลดลง 1
- ลบองค์ประกอบด้านบนออกจาก st
- ใส่ temp ลงใน 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
