Hướng dẫn giải của [VT Thiếu nhi] BÀI 16: 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
Đặt ~P_k = A_1 + \dots + A_k~ và ~S~ là tổng tất cả gói. An nhận ~P_k~, Bình nhận ~S - P_k~, nên chênh lệch là ~|S - 2P_k|~. Cần chọn ~k~ từ ~1~ đến ~N~ sao cho chênh lệch nhỏ nhất. Tổng có thể lên tới ~2 \cdot 10^{14}~ nên dùng long long.
Sub 1: Vét cạn — ~O(N^2)~, dùng khi ~N \le 2000~
Với mỗi ~k~ tính lại ~P_k~ bằng cách cộng từ đầu, rồi cập nhật chênh lệch nhỏ nhất. Nếu chỉ nộp sub này: đúng 10/20 test.
Sub 2: Tổng tiền tố — ~O(N)~
Cộng dồn ~P_k~ khi duyệt ~k~ và cập nhật chênh lệch nhỏ nhất ngay. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc dữ liệu. Nếu ~N \le 2000~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> A;
// Sub 1: vet can. Voi moi k, tinh tong A[1..k] bang cach cong lai tu dau. O(n^2).
// Dung khi n <= 2000.
void sub1() {
long long total = 0;
for (int i = 0; i < n; i++) total += A[i];
long long best = LLONG_MAX;
for (int k = 1; k <= n; k++) {
long long s = 0;
for (int i = 0; i < k; i++) s += A[i]; // phan cua An
best = min(best, llabs(total - 2 * s)); // chenh lech = |(tong - s) - s|
}
cout << best << "\n";
}
// Sub 2: tong tien to. Cong don tung goi, moi k xet ngay, O(n).
void sub2() {
long long total = 0;
for (int i = 0; i < n; i++) total += A[i];
long long best = LLONG_MAX, s = 0;
for (int k = 1; k <= n; k++) {
s += A[k - 1]; // s = tong A[1..k]
best = min(best, llabs(total - 2 * s));
}
cout << best << "\n";
}
int main() {
freopen("CANDY.INP", "r", stdin);
freopen("CANDY.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
A.resize(n);
for (int i = 0; i < n; i++) cin >> A[i];
if (n <= 2000) sub1();
else sub2();
return 0;
}
Bình luận