Hướng dẫn giải của [Beginner Free Contest 02] CANDY
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
Cho N gói kẹo, gói thứ i có A_i viên. Chọn k (1 ≤ k ≤ N): An nhận các gói 1..k, Bình nhận phần còn lại. Tìm chênh lệch nhỏ nhất có thể giữa số kẹo của hai người.
Sub 1: Vét cạn — ~O(n^2)~
Thử lần lượt mọi k. Với mỗi k, cộng lại số kẹo của An (gói 1..k) và của Bình (gói k+1..N) rồi lấy trị tuyệt đối của hiệu. Lấy giá trị nhỏ nhất trong các k. Đạt đúng nhưng chậm, đạt được 5/10 test (chỉ các test nhỏ, N ≤ 2000).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
long long best = LLONG_MAX;
// Thu tung k: tinh lai tong An va Binh bang vong lap
for (int k = 1; k <= n; k++) {
long long sumA = 0, sumB = 0;
for (int i = 0; i < k; i++) sumA += a[i];
for (int i = k; i < n; i++) sumB += a[i];
best = min(best, llabs(sumA - sumB));
}
cout << best << endl;
return 0;
}
Sub 2: Cộng dồn tiền tố (prefix sum) — ~O(n)~
Gọi S là tổng kẹo của An, T là tổng kẹo cả hai. Bình nhận T - S, nên chênh lệch là |S - (T - S)| = |2S - T|. Chỉ cần tính T một lần, rồi duyệt k và cộng dồn S bằng một biến. Mỗi k chỉ mất O(1).
Bẫy cần chú ý: 2·S có thể lên tới 4·10^14 nên phải dùng long long. Đạt 10/10 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
long long total = 0;
for (auto &x : a) {
cin >> x;
total += x;
}
// Gọi S là tổng các gói đầu tiên (An nhận 1..k).
// Chênh lệch = |S - (total - S)| = |2S - total|.
// Duyệt k và cộng dồn S bằng biến prefix, O(N).
long long prefix = 0, best = LLONG_MAX;
for (int k = 0; k < n; k++) {
prefix += a[k];
best = min(best, llabs(2 * prefix - total));
}
cout << best << endl;
return 0;
}
Bình luận