Hướng dẫn giải của [200 đề thầy Đức] Bài 152: Tổng độ lệ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ổng ~|a_1 - a_2| + \dots + |a_N - a_1|~ luôn viết được dưới dạng ~\sum c_i a_i~ với ~c_i \in \{-2, 0, 2\}~ và ~\sum c_i = 0~. Với ~N~ chẵn, lấy ~N/2~ số lớn nhất có hệ số ~+2~ và ~N/2~ số nhỏ nhất có hệ số ~-2~. Với ~N~ lẻ có thêm một số hệ số ~0~, cần thử từng số đó.
Sub 1: Thử từng phần tử giữa — ~O(N^2)~, dùng khi ~N \le 1000~
Sắp xếp, với ~N~ lẻ thử bỏ từng phần tử (hệ số ~0~), phần còn lại chia đều thành nửa lớn và nửa nhỏ. Nếu chỉ nộp sub này: đúng 13/21 test.
Sub 2: Tổng tiền tố — ~O(N \log N)~
Dùng mảng tổng tiền tố đã sắp xếp để tính nhanh tổng nửa lớn và nửa nhỏ khi bỏ phần tử ~k~ bất kỳ. Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
Nếu ~N \le 1000~ dùng sub 1, còn lại dùng sub 2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int N;
vector<long long> a; // day can sap xep
// Sub 1: O(N^2). Sap xep, voi N chan thi tong = 2*(m so lon nhat - m so nho nhat).
// Voi N le co mot phan tu "dung giua" co he so 0: thu lan luot bo tung phan tu, lay truong hop tot nhat.
void sub1() {
vector<long long> s = a;
sort(s.begin(), s.end());
int m = N / 2;
if (N % 2 == 0) {
long long big = 0, small = 0;
for (int i = 0; i < m; i++) { small += s[i]; big += s[N - 1 - i]; }
cout << 2 * (big - small) << "\n";
return;
}
long long best = 0;
for (int k = 0; k < N; k++) {
vector<long long> b;
for (int i = 0; i < N; i++) if (i != k) b.push_back(s[i]);
long long small = 0, big = 0;
for (int i = 0; i < m; i++) { small += b[i]; big += b[2 * m - 1 - i]; }
best = max(best, 2 * (big - small));
}
cout << best << "\n";
}
// Sub 2: O(N log N) — dung tong tien to de tinh nhanh moi truong hop bo phan tu k
void sub2() {
vector<long long> s = a;
sort(s.begin(), s.end());
int m = N / 2;
vector<long long> P(N + 1, 0);
for (int i = 0; i < N; i++) P[i + 1] = P[i] + s[i];
if (N % 2 == 0) {
cout << 2 * ((P[N] - P[m]) - P[m]) << "\n";
return;
}
long long best = 0;
for (int k = 0; k < N; k++) {
long long small, big;
if (k <= m) { small = P[m + 1] - s[k]; big = P[N] - P[m + 1]; }
else { small = P[m]; big = (P[N] - P[m]) - s[k]; }
best = max(best, 2 * (big - small));
}
cout << best << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> N;
a.assign(N, 0);
for (auto &x : a) cin >> x;
if (N <= 1000) sub1();
else sub2();
}
return 0;
}
Bình luận