Hướng dẫn giải của Diện tích lớn nhất
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Để tạo hình chữ nhật (hoặc vuông) từ 4 đoạn, cần chọn 2 cặp đoạn bằng nhau, diện tích là tích hai độ dài của hai cặp. Muốn diện tích lớn nhất thì chọn hai cặp có độ dài lớn nhất.
Sub 1: Vét cạn cặp — ~O(n^2)~, dùng khi ~n \le 1000~
Duyệt các cặp đoạn bằng nhau chưa dùng để lập danh sách các cặp, rồi thử mọi cặp hai cặp trong danh sách và lấy tích lớn nhất.
Nếu chỉ nộp sub này: đúng 11/20 test.
Sub 2: Sắp xếp — ~O(n \log n)~
Sắp xếp độ dài, lấy các cặp bằng nhau (mỗi cặp lấy 2 đoạn), sau đó đáp án là tích của hai cặp liên tiếp lớn nhất.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Dữ liệu ~n \le 1000~ dùng sub 1, còn lại dùng sub 2. Đề không nói rõ trường hợp không có hai cặp; chương trình in 0 trong trường hợp này.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> A;
// Hinh chu nhat (hoac vuong) can 2 cap doan bang nhau: canh a va canh b, dien tich a*b.
// Sub 1: vet can O(n^2) de lap cac cap doan bang nhau roi thu moi cap cap da chon. Dung khi n <= 1000.
void sub1() {
vector<bool> used(n, false);
vector<long long> pairs; // gia tri cua moi cap (moi cap dung 2 doan rieng)
for (int i = 0; i < n; i++) {
if (used[i]) continue;
for (int j = i + 1; j < n; j++) {
if (!used[j] && A[j] == A[i]) {
used[i] = used[j] = true;
pairs.push_back(A[i]);
break;
}
}
}
long long best = 0;
for (size_t i = 0; i < pairs.size(); i++)
for (size_t j = i + 1; j < pairs.size(); j++)
best = max(best, pairs[i] * pairs[j]);
cout << best << "\n";
}
// Sub 2: sap xep, lay cac cap doan bang nhau (moi gia tri lay floor(c/2) cap), roi
// dien tich lon nhat la tich cua hai cap lien tiep lon nhat. O(n log n).
void sub2() {
vector<long long> B = A;
sort(B.begin(), B.end());
vector<long long> pairs;
for (int i = 0; i + 1 < n; ) {
if (B[i] == B[i + 1]) {
pairs.push_back(B[i]);
i += 2; // lay 2 doan lam 1 cap
} else {
i++;
}
}
// pairs dang tang dan; hai cap lon nhat cho tich lon nhat
long long best = 0;
for (size_t i = 0; i + 1 < pairs.size(); i++)
best = max(best, pairs[i] * pairs[i + 1]);
cout << best << "\n";
}
int main() {
cin >> n;
A.resize(n);
for (int i = 0; i < n; i++) cin >> A[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận