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