数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中的汽车车队
假设有N辆汽车要沿着一条单车道公路行驶到同一个目的地。目的地距离为‘target’英里。现在每辆汽车i都有一个恒定的速度值speed[i]（以英里/小时为单位），并且初始位置是position[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
- temp := (t – v[i]的第一个元素) / v[i]的第二个元素
- 当st不为空且栈顶<= temp时
- 将ret减少1
- 从st中删除顶部元素
- 将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
更新于： 2020年5月5日
435 次查看
广告