Hướng dẫn giải của [200 đề thầy Đức] Bài 172: Độ lệch tối đa
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ìm độ lệch lớn nhất giữa hai phần tử bất kỳ của dãy và số cặp vị trí đạt độ lệch đó. Độ lệch lớn nhất bằng max trừ min.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 3000~
Thử mọi cặp ~i < j~, tính ~|b_i - b_j|~, giữ độ lệch lớn nhất và đếm số cặp đạt nó. Nếu chỉ nộp sub này: đúng 13/23 test.
Sub 2: Đếm min và max — ~O(n)~
Cặp đạt độ lệch lớn nhất phải gồm một vị trí có giá trị nhỏ nhất và một vị trí có giá trị lớn nhất, nên số cách là ~cnt_{min} \cdot cnt_{max}~. Trường hợp đặc biệt: nếu mọi số bằng nhau thì độ lệch là 0 và số cặp là ~n(n-1)/2~, cần dùng long long vì có thể lên tới khoảng ~2 \cdot 10^{10}~. Nếu chỉ nộp sub này: đúng 23/23 test.
Chương trình hoàn chỉnh
main đọc ~n~ và dãy. Nếu ~n \le 3000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long b[200005];
// Sub 1: vét cạn O(n^2). Thử mọi cặp (i, j), i < j.
void sub1() {
long long best = -1, cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) {
long long d = llabs(b[i] - b[j]);
if (d > best) {
best = d;
cnt = 1;
} else if (d == best) {
cnt++;
}
}
printf("%lld %lld\n", best, cnt);
}
// Sub 2: O(n). Độ lệch lớn nhất là max - min. Cặp đạt độ lệch đó gồm một vị trí min và một vị trí max.
void sub2() {
long long mn = b[1], mx = b[1];
for (int i = 2; i <= n; i++) {
mn = min(mn, b[i]);
mx = max(mx, b[i]);
}
long long cntMin = 0, cntMax = 0;
for (int i = 1; i <= n; i++) {
if (b[i] == mn) cntMin++;
if (b[i] == mx) cntMax++;
}
long long cnt;
if (mn == mx) cnt = (long long)n * (n - 1) / 2; // mọi cặp đều có độ lệch 0
else cnt = cntMin * cntMax;
printf("%lld %lld\n", mx - mn, cnt);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> b[i];
if (n <= 3000) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
return 0;
}
Bình luận