मान लीजिए कि ऐसी N कारें हैं जो एक लेन वाली सड़क के साथ एक ही गंतव्य तक जा रही हैं। गंतव्य 'लक्ष्य' मील दूर है। अब प्रत्येक कार में एक स्थिर गति मान गति [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 की सीमा में
- v में डालें (p[i], s[i])
- रिट:=n
- सॉर्ट वी सरणी
- एक स्टैक सेंट परिभाषित करें
- मैं के लिए 0 से n - 1 की सीमा में
- अस्थायी:=(t - v[i] का पहला तत्व) / v[i] का दूसरा तत्व
- जबकि सेंट खाली नहीं है और स्टैक टॉप <=अस्थायी
- रेट को 1 से घटाएं
- सेंट से शीर्ष तत्व हटाएं
- अस्थायी को सेंट में डालें
- रिटर्न रिट।
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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