Hướng dẫn giải của [200 đề thầy Đức] Bài 144: Đếm cặp số
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
Đếm số cặp chỉ số i < j thỏa mãn i × A[i] > j × A[j]. Với N ≤ 100 và T ≤ 100, cách thẳng nhất là thử mọi cặp.
Sub 1: Vét cạn — ~O(N^2)~
Duyệt mọi cặp (i, j) với i < j, kiểm tra trực tiếp điều kiện rồi đếm. Đạt đủ 21/21 test (cách này đã đủ nhanh vì N ≤ 100).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
long long cnt = 0;
// Vét cạn: thử mọi cặp (i, j) với i < j
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if ((long long)i * a[i] > (long long)j * a[j]) cnt++;
cout << cnt << "\n";
}
return 0;
}
Sub 2: Đếm nghịch thế bằng merge sort — ~O(N log N)~
Đặt b[k] = k × A[k]. Khi đó bài toán trở thành đếm cặp i < j có b[i] > b[j], tức là đếm nghịch thế của dãy b. Nghịch thế được đếm trong O(N log N) bằng merge sort: khi ghép hai nửa, nếu b[i] > b[j] thì mọi phần tử còn lại của nửa trái đều lớn hơn b[j] nên cộng thêm m - i.
Bẫy cần chú ý: k × A[k] tối đa khoảng 100 × 1000 = 10^5, không tràn số. Dùng so sánh nghiêm ngặt > vì đề yêu cầu >, các phần tử bằng nhau không được tính. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
// Đặt b[k] = k * A[k]. Bài toán trở thành đếm cặp i < j với b[i] > b[j]
// (nghịch thế). Dùng merge sort để đếm nghịch thế trong O(N log N).
long long cntInv(vector<long long> &b, vector<long long> &tmp, int l, int r) {
if (r - l <= 1) return 0;
int m = (l + r) / 2;
long long res = cntInv(b, tmp, l, m) + cntInv(b, tmp, m, r);
int i = l, j = m, k = l;
while (i < m && j < r) {
if (b[i] > b[j]) {
// b[i..m-1] đều lớn hơn b[j] (và đứng trước j)
res += m - i;
tmp[k++] = b[j++];
} else {
tmp[k++] = b[i++];
}
}
while (i < m) tmp[k++] = b[i++];
while (j < r) tmp[k++] = b[j++];
for (int x = l; x < r; x++) b[x] = tmp[x];
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<long long> b(n), tmp(n);
for (int k = 0; k < n; k++) {
long long x;
cin >> x;
b[k] = (long long)k * x;
}
cout << cntInv(b, tmp, 0, n) << "\n";
}
return 0;
}
Bình luận