ধরুন 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
- পরিসরে
- v তে (p[i], s[i]) ঢোকান
- ret :=n
- সর্ট v অ্যারে
- একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন
- আমি 0 থেকে n – 1
- পরিসরে
- temp :=(t – v[i] এর প্রথম উপাদান) / v[i] এর দ্বিতীয় উপাদান
- যখন st খালি নেই এবং স্ট্যাক টপ <=temp
- রেট 1 কম করুন
- st থেকে শীর্ষ উপাদান মুছুন
- st-এ temp সন্নিবেশ করুন
- রিটার্ন রিটার্ন।
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
