โปรแกรม C++ หาจำนวนคู่พิกัดที่ทำได้

สมมติว่าเราได้รับพิกัด 2n บนระนาบสองมิติ พิกัด 2n แบ่งออกเป็นสองอาร์เรย์ coordA และ coordB พิกัดจะแสดงเป็นคู่จำนวนเต็ม ตอนนี้เราต้องสร้างคู่พิกัดที่จะประกอบด้วยหนึ่งจุดจาก coordA และหนึ่งจุดจาก coordB เราสามารถสร้างคู่ได้ก็ต่อเมื่อพิกัด x ของจุดจาก coordA น้อยกว่าจุดจาก coordB และพิกัด y ของจุดจาก coordA นั้นเล็กกว่าของจุดจาก coordB เราต้องค้นหาจำนวนคู่ที่เราสามารถสร้างได้ และจุดหนึ่งไม่สามารถอยู่ในหลายคู่ได้

ดังนั้น หากอินพุตเป็น n =3, coordsA ={{1, 3}, {2, 4}, {4, 3}}, coordsB ={{2, 2}, {4, 2}, {0 , 2}} แล้วผลลัพธ์จะเป็น 1

คู่เดียวที่ทำได้คือ (1, 3) และ (0, 2).

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

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)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

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

ผลลัพธ์

1