मान लीजिए हमारे पास N कोऑर्डिनेट पॉइंट्स P की एक लिस्ट है जो (xi, yi) के रूप में है। 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]
चरण
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
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,
