Computer >> Máy Tính >  >> Lập trình >> C ++

Đội xe trong C ++

Giả sử có N ô tô đang đi đến cùng một điểm đến trên một con đường có một làn đường. Đích đến cách đó hàng dặm. Bây giờ mỗi ô tô tôi có giá trị tốc độ không đổi là tốc độ [i] (tính bằng dặm / giờ) và vị trí ban đầu là vị trí [i] dặm về phía mục tiêu dọc theo con đường.

Một chiếc ô tô không bao giờ có thể vượt qua một chiếc xe khác phía trước, nhưng nó có thể đuổi kịp nó và lái xe vượt qua cùng một tốc độ. Ở đây khoảng cách giữa hai chiếc xe này được bỏ qua - chúng được cho là có cùng một vị trí. Một đoàn ô tô là một tập hợp không rỗng gồm các ô tô chạy cùng một vị trí và cùng vận tốc. Nếu một ô tô đuổi kịp đoàn ô tô ngay tại điểm đến thì ô tô đó vẫn được coi là đoàn ô tô. Vì vậy, chúng ta phải tìm xem có bao nhiêu đoàn xe sẽ đến đích.

Vì vậy, nếu mục tiêu là 12, nếu vị trí là [10,8,0,5,3] và tốc độ là [2,4,1,1,3] thì kết quả đầu ra sẽ là 3. Điều này là do xe ô tô bắt đầu từ 10 và 8 trở thành một đội, gặp nhau lúc 12. Bây giờ ô tô bắt đầu từ số 0 không đuổi kịp bất kỳ ô tô nào khác, vì vậy nó là một đội xe tự nó. Một lần nữa những chiếc xe xuất phát lúc 5 và 3 trở thành một đội, gặp nhau lúc 6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Tạo một mảng v, n:=kích thước của mảng vị trí p
  • cho tôi trong phạm vi từ 0 đến n - 1
    • insert (p [i], s [i]) vào v
  • ret:=n
  • sắp xếp v mảng
  • xác định một ngăn xếp
  • cho tôi trong phạm vi từ 0 đến n - 1
    • temp:=(t - phần tử đầu tiên của v [i]) / phần tử thứ hai của v [i]
    • while st không trống và đỉnh ngăn xếp <=temp
      • giảm ret xuống 1
      • xóa phần tử hàng đầu khỏi st
    • chèn tạm thời vào st
  • trả lời lại.

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

12
[10,8,0,5,3]
[2,4,1,1,3]

Đầu ra

3