特定の操作で各都市から訪問できる都市の数をカウントするC++プログラム

（xi、yi）の形式でN個の座標点Pのリストがあるとします。 x値とy値は、最初のN個の自然数の順列です。 1からNの範囲のkごとに。都市kにいます。操作は何度でも任意に適用できます。操作：現在の都市よりもx座標が小さく、y座標が小さい、またはx座標が大きい、またはy座標が大きい別の都市に移動します。都市kから到達できる都市の数を見つける必要があります。 。

したがって、入力がP =[[1、4]、[2、3]、[3、1]、[4、2]]の場合、出力は[1、1、2、2]<になります。 / P>

ステップ

これを解決するには、次の手順に従います-

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]

例

理解を深めるために、次の実装を見てみましょう-

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

入力

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

出力

1, 1, 2, 2,