C++での車のフリート

1車線の道路に沿って同じ目的地に向かうN台の車があるとします。目的地は「ターゲット」マイル離れています。これで、各車iの速度値は一定のspeed [i]（マイル/時）になり、初期位置は道路に沿ってターゲットに向かって位置[i]マイルになります。

車が前方の別の車を追い越すことはできませんが、それに追いつき、同じ速度でバンパーからバンパーへと追いつくことができます。ここでは、これら2台の車の間の距離は無視されます-それらは同じ位置にあると想定されます。車のフリートは、同じ位置と同じ速度で運転する空でない車のセットです。 1台の車が目的地で車のフリートに追いついた場合でも、1台の車のフリートと見なされます。そのため、目的地に到着する車の数を見つける必要があります。

したがって、ターゲットが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の場合
  • （p [i]、s [i]）をvに挿入
• ret：=n
• ソートv配列
• スタックstを定義する
• 0からn–1の範囲のiの場合
  • temp：=（t – v [i]の最初の要素）/v[i]の2番目の要素
  • stが空ではなく、スタックトップ<=temp
    • retを1減らします
    • stから最上位の要素を削除
  • 温度をstに挿入
• returnret。

理解を深めるために、次の実装を見てみましょう-

例

#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