Giả sử, chúng ta có 2n số tọa độ trên một mặt phẳng hai chiều. Tọa độ 2n được chia thành hai mảng coordA và coordB. Các tọa độ được biểu diễn dưới dạng các cặp số nguyên. Bây giờ chúng ta phải tạo các cặp tọa độ sẽ chứa một điểm từ coordA và một điểm từ coordB. Chúng ta có thể tạo cặp nếu và chỉ khi tọa độ x của điểm từ coordA nhỏ hơn tọa độ của điểm từ coordB và tọa độ y của điểm từ coordA nhỏ hơn tọa độ của điểm từ coordB. Chúng ta phải tìm ra số lượng các cặp mà chúng ta có thể thực hiện và một điểm không thể thuộc về nhiều cặp.
Vì vậy, nếu đầu vào là n =3, coordsA ={{1, 3}, {2, 4}, {4, 3}}, coordsB ={{2, 2}, {4, 2}, {0 , 2}}, thì đầu ra sẽ là 1.
Cặp duy nhất có thể được tạo là (1, 3) và (0, 2).
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
Define an array chk of size: 100 initialized with 0 sort the array coordA sort the array coordB k := 0 for initialize i := n - 1, when i >= 0, update (decrease i by 1), do: for initialize j := 0, when j < n, update (increase j by 1), do: if chk[j] is same as 0 and first value of coordA[i] < second value of coordB[j] and second value of coordA[i] < first value of coordB[j], then: chk[j] := 1 (increase k by 1) Come out from the loop print(k)
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;
const int INF = 1e9;
#define N 100
void solve(int n, vector<pair<int,int>> coordA, vector<pair<int,int>>coordB){
int i, j, k;
int chk[100] = {0};
sort(coordA.begin(),coordA.end());
sort(coordB.begin(),coordB.end());
k = 0;
for(i = n - 1; i >= 0; i--) {
for(j = 0; j < n; j++) {
if(chk[j] == 0 && coordA[i].first < coordB[j].second && coordA[i].second < coordB[j].first) {
chk[j] = 1;
k++;
break;
}
}
}
cout<< k;
}
int main() {
int n = 3;
vector<pair<int,int>> coordsA = {{1, 3}, {2, 4}, {4, 3}};
vector<pair<int,int>> coordsB = {{2, 2}, {4, 2}, {0, 2}};
solve(n, coordsA, coordsB);
return 0;
} Đầu vào
3, {{1, 3}, {2, 4}, {4, 3}}, {{2, 2}, {4, 2}, {0, 2}} Đầu ra
1