C ++程序找出可以制作的坐标对的数量

• Z时代
• 2024-01-10
• 分类：综合

假设我们在一个二维平面上有 2n 个坐标。2n 个坐标分为两个数组 coordA 和 coordB。坐标表示为整数对。现在我们必须形成坐标对，其中包含一个来自 coordA 的点和一个来自 coordB 的点。当且仅当来自 coordA 的点的 x 坐标小于来自 coordB 的点的 x 坐标，并且来自 coordA 的点的 y 坐标小于来自 coordB 的点的 x 坐标时，我们才能配对。我们必须找出我们可以制作的对数，一个点不能属于多个对。

所以，如果输入像 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

以上是 C ++程序找出可以制作的坐标对的数量 的全部内容， 来源链接： utcz.com/z/297178.html