Hướng dẫn giải của [200 đề thầy Đức] Bài 151: Tổng nhỏ nhất của các tích
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
Cần ghép các số của dãy ~a~ với các số của dãy ~b~ (đổi thứ tự cả hai dãy) sao cho tổng các tích nhỏ nhất. Ta ghép số nhỏ nhất của ~a~ với số lớn nhất của ~b~, số nhỏ thứ hai với số lớn thứ hai, và cứ thế. Tổng có thể lên tới ~10^{17}~ nên dùng long long.
Sub 1: Ghép tham lam bằng vòng lặp tìm min — ~O(N^2)~
Sắp xếp ~a~ tăng dần. Lần lượt lấy số ~a~ lớn nhất còn lại, rồi tìm số ~b~ nhỏ nhất chưa dùng bằng cách quét toàn bộ dãy. Cách này đúng nhưng ~O(N^2)~ nên với N lên tới 10^5 và T lên tới 100 nó quá giờ. Khi chấm, sub này không kết thúc trong thời gian chờ (chưa đo được số test đạt).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
int n;
cin >> n;
vector<long long> a(n), b(n);
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
// Vét cạn O(N^2): lần lượt lấy số a lớn nhất còn lại, ghép với b nhỏ nhất còn lại
vector<bool> used(n, false);
sort(a.begin(), a.end());
long long total = 0;
for (int i = n - 1; i >= 0; i--) {
int best = -1;
for (int j = 0; j < n; j++) {
if (!used[j] && (best == -1 || b[j] < b[best])) best = j;
}
used[best] = true;
total += a[i] * b[best];
}
cout << total << "\n";
}
return 0;
}
Sub 2: Sắp xếp một dãy tăng, một dãy giảm — ~O(N \log N)~
Sắp xếp ~a~ tăng dần và ~b~ giảm dần, rồi nhân từng cặp theo chỉ số và cộng lại. Đây là cách ghép tối ưu theo bất đẳng thức sắp xếp lại. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
int n;
cin >> n;
vector<long long> a(n), b(n);
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
// Ghép số a nhỏ nhất với số b lớn nhất, số tiếp theo với số tiếp theo
sort(a.begin(), a.end()); // a tăng dần
sort(b.begin(), b.end(), greater<long long>()); // b giảm dần
long long total = 0; // tối đa 10^5 * 10^12 = 10^17 nên dùng long long
for (int i = 0; i < n; i++) total += a[i] * b[i];
cout << total << "\n";
}
return 0;
}
Bình luận