数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++程序，用于计算可以生成的坐标对的数量
假设我们得到了二维平面上的2n个坐标。这2n个坐标被分成两个数组coordA和coordB。坐标表示为整数对。现在我们必须形成坐标对，其中包含来自coordA的一个点和来自coordB的一个点。当且仅当来自coordA的点的x坐标小于来自coordB的点的x坐标，并且来自coordA的点的y坐标小于来自coordB的点的y坐标时，我们才能构成对。我们必须找出可以构成的对的数量，并且一个点不能属于多个对。
因此，如果输入类似于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
更新于：2022年2月25日
892 次浏览
广告