สมมติว่าเรามีรายการ N จุดพิกัด P ในรูปแบบ (xi, yi) ค่า x และ y เป็นการเรียงสับเปลี่ยนของจำนวนธรรมชาติ N ตัวแรก สำหรับแต่ละ k ในช่วง 1 ถึง N เราอยู่ที่เมือง k เราสามารถประยุกต์ใช้การดำเนินการตามอำเภอใจได้หลายครั้ง ปฏิบัติการ:เราย้ายไปยังเมืองอื่นที่มีพิกัด x น้อยกว่าและพิกัด y เล็กกว่า หรือพิกัด x ที่ใหญ่กว่าหรือใหญ่กว่าเมืองที่เราอยู่ในปัจจุบัน เราต้องหาจำนวนเมืองที่เราสามารถเข้าถึงได้จากเมือง 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,
