C ++中的汽车舰队

假设有N辆汽车沿着一条车道行驶到相同的目的地。目的地是“目标”英里。现在,每辆汽车i都具有恒定的速度值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

    • 将ret降低1

    • 从st删除top元素

    • temp:=(t – v [i]的第一个元素)/ v [i]的第二个元素

    • 当st不为空且栈顶<= temp

    • 将temp插入st

  • 返回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]

输出结果

3