資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢將一個矩形插入另一個矩形後剩餘的最小矩形數量
假設我們有 N 個不同矩形的寬度和高度；我們必須找到將一個矩形插入另一個矩形後剩餘的最小矩形數量。因此，如果 W1 和 W2 分別是矩形 R1 和 R2 的寬度。並且 H1 和 H2 分別是 R1 和 R2 的高度，那麼如果 W1 < W2 且 H1 < H2，則矩形 R1 巢狀在矩形 R2 內。因此，最小的可以放入第二小的，然後放入下一個，依此類推。
因此，如果輸入類似於 {{ 30, 45 }, { 15, 15 }, { 45, 30 },{60, 75 }}，則輸出將為 2，因為一種可能的方式是將第二個矩形插入第一個矩形，然後將該矩形插入第四個。第三個和第四個矩形剩下。
為了解決這個問題，我們將遵循以下步驟：
n := 盒子的數量
根據大小對陣列 boxes 進行排序
定義一個儲存對的陣列 nested
將 boxes[n - 1] 插入到 nested 的末尾
對於初始化 i := n - 2，當 i >= 0 時，更新（i 減 1），執行以下操作：
right := nested 的大小
當 left <= right 時，執行以下操作：
mid := (right + left) / 2
如果 nested[mid] 的高度與 boxes[i] 的高度相同，或者 nested[mid] 的寬度 <= boxes[i] 的寬度，則：
left := mid + 1
否則
right := mid - 1
如果 left 等於 nested 的大小，則：
將 boxes[i] 插入到 nested 的末尾
否則
nested[left] 的寬度 := boxes[i] 的寬度
nested[left] 的高度 := boxes[i] 的高度
返回 nested 的大小
示例
讓我們看看以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
bool comp(const pair<int, int>& L, const pair<int, int>& R) {
if (L.first == R.first)
return L.second > R.second;
return L.first < R.first;
}
int Rectangles(vector<pair<int, int>> &boxes) {
int n = boxes.size();
sort(boxes.begin(), boxes.end(), comp);
vector<pair<int, int< < nested;
nested.push_back(boxes[n - 1]);
for (int i = n - 2; i >= 0; --i) {
int right = nested.size() - 1, left = 0;
while (left <= right) {
int mid = (right + left) / 2;
if (nested[mid].first == boxes[i].first || nested[mid].second <= boxes[i].second)
left = mid + 1;
else
right = mid - 1;
}
if (left == nested.size())
nested.push_back(boxes[i]);
else {
nested[left].second = boxes[i].second;
nested[left].first = boxes[i].first;
}
}
return nested.size();
}
int main() {
vector<pair<int, int>> boxes = {{30, 45}, {15,15}, {45,30},{60,75}};
cout << Rectangles(boxes);
}輸入
{{30, 45}, {15,15}, {45,30},{60,75}}輸出
2
155 次檢視
