Chương trình C++ đếm số thành phố có thể thăm từ mỗi thành phố với các phép toán cho trước

Giả sử chúng ta có một danh sách N điểm tọa độ P dưới dạng (xi, yi). Các 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 khoảng từ 1 đến N, chúng ta đang ở thành phố k. Chúng ta có thể áp dụng các phép toán bất kỳ số lần. Phép toán: Di 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 tọa độ y lớn hơn so với thành phố hiện tại. Ta phải tìm số thành phố có thể đến được từ thành phố k.

Ví dụ, 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

Để giải bài toán này, chúng ta thực hiện các bước sau:

n := kích thước của P
Khởi tạo mảng 2D lst
for i := 0; i < n; i++:
    v := { P[i, 0], P[i, 1], i }
    thêm v vào cuối lst
sắp xếp mảng lst
y_min := 1e9
Khởi tạo tập hợp se
Khởi tạo mảng ans kích thước n, điền 0
for i := 0; i < n; i++:
    y_min := min(y_min, lst[i, 1])
    thêm lst[i, 2] vào se
    nếu y_min + i == n:
        for mỗi phần tử j trong se:
            ans[j] := kích thước của se
        xóa tập hợp se
    nếu i == n - 1:
        for mỗi phần tử j trong se:
            ans[j] := kích thước của se
for i := 0; i < n; i++:
    hiển thị ans[i]

Ví dụ minh họa

Dưới đây là triển khai C++ để 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,