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