Giả sử chúng ta có n cặp hộp cần vận chuyển trong một container hình vuông. Chiều rộng của cặp hộp được cho dưới dạng cặp (a, b) và chúng được đưa vào một mảng 'dimensions'. Nếu chúng ta để chiều rộng của các hộp song song với nhau, chúng ta phải tìm diện tích mà các hộp sẽ chiếm bên trong container. Chúng ta không thể xếp chồng các hộp lên nhau. Chúng ta xác định diện tích tối thiểu cần thiết cho hai hộp trong container cho tất cả n cặp.
Ví dụ, nếu đầu vào là n = 4, dimensions = {{2, 4}, {3, 6}, {2, 5}, {4, 6}}, thì đầu ra sẽ là:
64 25 36 16
Các bước thực hiện
Để giải quyết bài toán này, chúng ta thực hiện theo các bước sau:
res := 0 while n khác 0, do: a := giá trị đầu tiên của dimensions[n] b := giá trị thứ hai của dimensions[n] res := maximum của (2 * minimum của (a, b) và maximum của a và b) in(res * res) n := n - 1
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; #define N 100 void solve(int n, vector<pair<int, int>> dimensions) { int res = 0; while(n--){ int a = dimensions[n].first; int b = dimensions[n].second; int res = max(2 * min(a, b), max(a, b)); cout<< res * res << endl; } } int main() { int n = 4; vector<pair<int, int>> dimensions = {{2, 4}, {3, 6}, {2, 5}, {4, 6}}; solve(n, dimensions); return 0; }Đầu vào
4, {{2, 4}, {3, 6}, {2, 5}, {4, 6}}Đầu ra
64 25 36 16