資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告