資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告