Chương trình C ++ để đếm số lượng thành phố mà chúng ta có thể ghé thăm từ mỗi thành phố với các phép toán nhất định

Giả sử chúng ta có một danh sách N tọa độ điểm P có dạng (xi, yi). Giá trị x và y là hoán vị của N số tự nhiên đầu tiên. Với mỗi k trong phạm vi từ 1 đến N. Chúng tôi đang ở thành phố k. Chúng ta có thể áp dụng các thao tác nhiều lần tùy ý. Phép toán:Chúng ta chuyển đến một thành phố khác có tọa độ x nhỏ hơn và tọa độ y nhỏ hơn hoặc tọa độ x lớn hơn hoặc lớn hơn y so với thành phố chúng ta đang ở. Chúng ta phải tìm số thành phố mà chúng ta có thể đến từ thành phố k .

Vì vậy, nếu đầu vào là P =[[1, 4], [2, 3], [3, 1], [4, 2]], thì đầu ra sẽ là [1, 1, 2, 2]

Các bước

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

n := size of P
Define one 2D array lst
for initialize i := 0, when i < n, update (increase i by 1), do:
   v := { P[i, 0], P[i, 1], i }
   insert v at the end of lst
sort the array lst
y_min := 1e9
Define one set se
Define an array ans of size n and fill with 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   y_min := minimum of y_min and lst[i, 1]
   insert lst[i, 2] into se
   if y_min + i is same as n, then:
      for each element j in se
         ans[j] := size of se
      clear the set se
   if i is same as n - 1, then:
      for each element j in se
         ans[j] := size of se
for initialize i := 0, when i < n, update (increase i by 1), do:
   display ans[i]

Ví dụ

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;

void solve(vector<vector<int>> P){
   int n = P.size();
   vector<vector<int>> lst;
   for (int i = 0; i < n; i++){
      vector<int> v = { P[i][0], P[i][1], i };
      lst.push_back(v);
   }
   sort(lst.begin(), lst.end());
   int y_min = 1e9;
   set<int> se;
   vector<int> ans(n, 0);
   for (int i = 0; i < n; i++){
      y_min = min(y_min, lst[i][1]);
      se.insert(lst[i][2]);
      if (y_min + i == n){
         for (auto j : se)
            ans[j] = se.size();
         se.clear();
      }
      if (i == n - 1){
         for (auto j : se)
            ans[j] = se.size();
      }
   }
   for (int i = 0; i < n; i++){
      cout << ans[i] << ", ";
   }
}
int main(){
   vector<vector<int>> P = { { 1, 4 }, { 2, 3 }, { 3, 1 }, { 4, 2 } };
   solve(P);
}

Đầu vào

{ { 1, 4 }, { 2, 3 }, { 3, 1 }, { 4, 2 } }

Đầu ra

1, 1, 2, 2,