Hướng dẫn giải của [VTT Q4 Contest 01] Bài 1: Bé tập vẽ [DRAW]
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 chọn một độ dài đích ~L~ sao cho tổng ~\sum |a_i - L|~ nhỏ nhất. Đây là bài toán kinh điển: đáp án đạt được khi ~L~ là trung vị của dãy.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 5000~
Thử lần lượt từng ~a_i~ làm độ dài đích (tổng hàm lồi theo ~L~ nên cực tiểu đạt tại một giá trị của dãy), với mỗi lần tính tổng chênh lệch trong ~O(n)~. Nếu chỉ nộp sub này: đúng 9/12 test.
Sub 2: Sắp xếp và lấy trung vị — ~O(n \log n)~
Sắp xếp dãy, chọn phần tử ở giữa ~a_{(n+1)/2}~ làm đích rồi cộng các độ lệch. Lưu ý tổng có thể lên tới ~2 \times 10^5 \cdot 10^9~ nên phải dùng long long. Nếu chỉ nộp sub này: đúng 12/12 test.
Chương trình hoàn chỉnh
main đọc dữ liệu; nếu ~n \le 5000~ gọi sub1, ngược lại gọi sub2. 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;
long long a[200005];
// Sub 1: thử mọi độ dài đích bằng một trong các a[i] — O(n^2)
void sub1() {
long long best = LLONG_MAX;
for (int i = 1; i <= n; i++) {
long long s = 0;
for (int j = 1; j <= n; j++) s += llabs(a[j] - a[i]);
best = min(best, s);
}
cout << best << "\n";
}
// Sub 2: sắp xếp, chọn trung vị — O(n log n)
void sub2() {
sort(a + 1, a + n + 1);
long long m = a[(n + 1) / 2], s = 0;
for (int i = 1; i <= n; i++) s += llabs(a[i] - m);
cout << s << "\n";
}
int main() {
freopen("DRAW.INP", "r", stdin);
freopen("DRAW.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 5000) sub1();
else sub2();
}
Bình luận