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

Thời gian cần thiết để thông báo cho tất cả nhân viên bằng C ++

Giả sử chúng ta có một công ty có n nhân viên với một ID duy nhất cho mỗi nhân viên. Các ID này nằm trong khoảng từ 0 đến n - 1. Người đứng đầu công ty là người có headID. Mỗi nhân viên có một người quản lý trực tiếp được cung cấp trong mảng người quản lý trong đó người quản lý [i] là người quản lý trực tiếp của nhân viên thứ i, manager [headID] =-1. Nó cũng được đảm bảo rằng các mối quan hệ cấp dưới có cấu trúc giống như cây. Ở đây người đứng đầu công ty muốn thông báo cho tất cả các nhân viên trong công ty một tin khẩn cấp. Anh ta có thể thông báo cho cấp dưới trực tiếp của mình và họ sẽ thông báo cho cấp dưới của mình và cứ tiếp tục như vậy cho đến khi tất cả nhân viên biết về tin khẩn cấp. Nhân viên thứ i cần Thời gian thông báo [i] phút để thông báo cho tất cả cấp dưới trực tiếp của mình (Vì vậy, sau Thời gian thông báo [i] phút, tất cả cấp dưới trực tiếp của anh ta có thể bắt đầu loan tin). Chúng tôi phải tìm số phút cần thiết để thông báo cho tất cả các nhân viên về tin tức khẩn cấp. Vì vậy, nếu đầu vào là n =6, headID =2, manager =[2,2, -1,2,2,2], infromTime =[0,0,1.0,0,0], thì đầu ra sẽ là 1.

Thời gian cần thiết để thông báo cho tất cả nhân viên bằng C ++

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

  • ret:=0

  • xác định một mảng được gọi là đồ thị có kích thước n, đặt root:=-1

  • cho tôi trong phạm vi 0 đến kích thước của mảng trình quản lý

    • u:=managet [i] và v:=i

    • nếu u là -1, thì hãy đặt root:=v và chuyển sang lần lặp tiếp theo

    • chèn v vào biểu đồ [u]

  • xác định hàng đợi q, chèn gốc vào q và xác định một mảng gọi là thời gian, có kích thước n

  • cho đến khi q không trống

    • curr:=phần tử phía trước của q và xóa phần tử phía trước khỏi q

    • nếu kích thước của danh sách biểu đồ [curr] là 0, thì hãy chuyển sang lần lặp tiếp theo

    • cho tôi trong phạm vi từ 0 đến kích thước của danh sách biểu đồ [curr]

      • chèn biểu đồ [curr, i] vào q

      • time [graph [curr, i]]:=time [curr] + InformTime [curr]

  • cho tôi trong phạm vi từ 0 đến n - 1:ret:=max của ret và thời gian [i]

  • trả lại ret

Ví dụ (C ++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
      int ret = 0;
      vector <int> graph[n];
      int root = -1;
      for(int i = 0; i < manager.size(); i++){
         int u = manager[i];
         int v = i;
         if(u == -1) {
            root = v;
            continue;
         }
         graph[u].push_back(v);
      }
      queue <int> q;
      q.push(root);
      vector <int> time(n);
      while(!q.empty()){
         int curr = q.front();
         q.pop();
         if(!graph[curr].size()) continue;
         for(int i = 0; i < graph[curr].size(); i++){
            q.push(graph[curr][i]);
            time[graph[curr][i]] = time[curr] + informTime[curr];
         }
      }
      for(int i = 0; i <n; i++)ret = max(ret, time[i]);
      return ret;
   }
};
main(){
   vector<int> v = {2,2,-1,2,2,2}, v1 = {0,0,1,0,0,0};
   Solution ob;
   cout << (ob.numOfMinutes(6, 2, v, v1));
}

Đầu vào 

6
2
[2,2,-1,2,2,2]
[0,0,1,0,0,0]

Đầu ra 

1