C++-এ কার ফ্লিট সমস্যা সমাধান

মান করুন Nটি গাড়ি একই লেনের রাস্তা দিয়ে একই গন্তব্যে যাচ্ছে। গন্তব্য target মাইল দূরত্বে। প্রতিটি গাড়ি i-এর একটি কনস্ট্যান্ট গতি আছে speed[i] (মাইল প্রতি ঘন্টা), এবং প্রাথমিক অবস্থান position[i] মাইল গন্তব্যের দিকে রাস্তার দিক থেকে।

একটি গাড়ি অন্য গাড়িকে ওভারটেক করতে পারে না, তবে এটি পেছনে থেকে ধাক্কা দিতে পারে এবং একই গতিতে বাম্পার-টু-বাম্পার চলে। এখানে দুটি গাড়ির মধ্যবর্তী দূরত্ব উপেক্ষা করা হয় - একই অবস্থান এবং গতি ধরা হয়। একটি কার ফ্লিট হল কিছু নন-ইম্পটি গাড়ির সেট যা একই অবস্থান এবং গতিতে চলে। যদি একটি গাড়ি গন্তব্য পয়েন্টে কার ফ্লিটকে ধাক্কা দেয়, তবে সেটিও একই কার ফ্লিট হিসেবে বিবেচিত হবে। আমাদের বের করতে হবে কতগুলো কার ফ্লিট গন্তব্যে পৌঁছাবে।

যদি target = 12, position = [10,8,0,5,3] এবং speed = [2,4,1,1,3] হয়, তবে আউটপুট হবে 3। কারণ 10 এবং 8 পজিশনের গাড়িগুলো একটি ফ্লিট হয়ে 12-এ মিলিত হয়। 0 পজিশনের গাড়ি অন্য কোনো গাড়িকে ধাক্কা দেয় না, তাই এটি একা একটি ফ্লিট। আবার 5 এবং 3 পজিশনের গাড়িগুলো একটি ফ্লিট হয়ে 6-এ মিলিত হয়।

এটি সমাধান করার জন্য নিচের ধাপগুলি অনুসরণ করুন −

একটি অ্যারে v তৈরি করুন, n := position অ্যারের আকার p
i = 0 থেকে n - 1 পর্যন্ত
- (p[i], s[i]) v-তে ইনসার্ট করুন
ret := n
v অ্যারে সর্ট করুন
একটি স্ট্যাক st সংজ্ঞায়িত করুন
i = 0 থেকে n - 1 পর্যন্ত
- temp := (t - v[i].first) / v[i].second
- যতক্ষণ st খালি না এবং স্টকের টপ = temp
  - ret 1 কমান
  - স্টকে থেকে টপ এলিমেন্ট ডিলিট করুন
- temp স্টকে পুশ করুন
ret ফেরত দিন

উদাহরণ কোড

#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]