Hướng dẫn giải của [2526 KS2 THCS] Bài 1: Chia nhóm cân bằng [BAI1]
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
Ba vật có khối lượng A, B, C được chia thành hai nhóm (mỗi nhóm gồm một hoặc hai vật). Được thêm một vật khối lượng x ≥ 0 vào một nhóm bất kỳ sao cho độ chênh lệch hai nhóm không vượt quá D. Tìm x nhỏ nhất.
Sub 1: Vét cạn theo x — ~O(A + B + C)~
Thử x = 0, 1, 2, … . Với mỗi x, xét 3 cách chia 3 vật gốc thành 2 nhóm khác rỗng, rồi thử thêm x vào nhóm 1 hoặc nhóm 2 và kiểm tra độ chênh lệch có ≤ D. Trả về x đầu tiên thoả mãn. Chạy đúng nhưng chậm khi tổng khối lượng lớn (subtask 1: A+B+C ≤ 10^6).
Kết quả chấm: 14/21 (SUB ok 14/21, TLE 7, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long A, B, C, D;
cin >> A >> B >> C >> D;
long long v[3] = {A, B, C};
long long tong = A + B + C;
// Vet can: thu x = 0, 1, 2, ... ; voi moi cach chia 3 vat thanh 2 nhom khac rong,
// thu them x vao nhom 1 hoac nhom 2, kiem tra do lech <= D.
for (long long x = 0; x <= tong; x++) {
bool ok = false;
for (int mask = 1; mask <= 6 && !ok; mask++) { // tap con khac rong, khac toan bo
long long s1 = 0;
for (int i = 0; i < 3; i++) if (mask >> i & 1) s1 += v[i];
long long s2 = tong - s1;
if (llabs((s1 + x) - s2) <= D) ok = true; // them x vao nhom 1
if (llabs(s1 - (s2 + x)) <= D) ok = true; // them x vao nhom 2
}
if (ok) { cout << x << "\n"; return 0; }
}
cout << tong << "\n";
return 0;
}
Sub 2: Công thức — ~O(1)~
Với một cách chia có nhóm đơn là vật v, độ chênh là |v - (tổng - v)|. Thêm x vào nhóm nhẹ hơn sẽ giảm độ chênh đi x, nên x nhỏ nhất cần là max(0, |độ chênh| - D). Lấy giá trị nhỏ nhất trong 3 cách chia. Dùng long long.
Kết quả chấm: 21/21 (PASS 21/21)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long A, B, C, D;
cin >> A >> B >> C >> D;
long long tong = A + B + C;
// Chia 3 vat goc thanh 2 nhom: mot vat mot nhom, hai vat mot nhom.
// Voi vat don v, do lech |delta| = |v - (tong - v)|.
// Them vat x vao nhom nhe hon thi do lech giam di x, nen x nho nhat = max(0, |delta| - D).
// Chon cach chia cho ket qua nho nhat.
long long ans = LLONG_MAX;
long long v[3] = {A, B, C};
for (int i = 0; i < 3; i++) {
long long delta = llabs(v[i] - (tong - v[i]));
ans = min(ans, max(0LL, delta - D));
}
cout << ans << "\n";
return 0;
}
Bình luận