Hướng dẫn giải của [200 đề thầy Đức] Bài 64: Đi taxi
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~ nhóm, nhóm thứ ~i~ có ~a_i \in [1, 4]~ người. Mỗi taxi chở tối đa 4 khách và không được tách nhóm. Tìm số taxi ít nhất.
Sub 1: Quy hoạch bitmask — ~O(3^n)~, dùng khi ~n \le 17~
Đặt ~dp[S]~ là số taxi ít nhất để chở các nhóm trong tập ~S~. Với mỗi tập, xét taxi chở nhóm có chỉ số thấp nhất và một tập con các nhóm còn lại có tổng người không vượt quá 4. Sub này chỉ dùng được với ~n~ nhỏ vì số trạng thái tăng theo ~2^n~.
Nếu chỉ nộp sub này: đúng 1/20 test.
Sub 2: Tham lam theo số người — ~O(n)~, dùng khi mọi trường hợp còn lại
Đếm số nhóm 1, 2, 3, 4 người. Nhóm 4 và nhóm 3 mỗi nhóm một taxi, taxi của nhóm 3 còn chỗ cho một nhóm 1. Nhóm 2 ghép từng cặp một taxi; nhóm 2 lẻ chiếm một taxi còn chỗ cho hai nhóm 1. Nhóm 1 còn lại xếp 4 người một taxi.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Chương trình đọc ~n~ và các ~a_i~. Nếu ~n \le 17~ thì gọi sub1, ngược lại gọi sub2. Ví dụ: các nhóm ~1, 2, 4, 3, 3~ cần 4 taxi; các nhóm ~2, 3, 4, 4, 2, 1, 3, 1~ cần 5 taxi.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a; // a[i]: so nguoi cua nhom thu i (1..4)
// Sub 1: vet can quy hoach bitmask. dp[mask] = so taxi it nhat de cho cac nhom trong mask.
// Taxi chua nhom dau tien (bit thap nhat) cua mask, them mot tap con s sao cho tong <= 4.
// O(3^n), dung khi n <= 17.
void sub1() {
int full = (1 << n) - 1;
vector<int> sum(1 << n, 0), dp(1 << n, INT_MAX);
for (int mask = 1; mask <= full; mask++)
sum[mask] = sum[mask & (mask - 1)] + a[__builtin_ctz(mask)]; // tong so nguoi trong tap mask
dp[0] = 0;
for (int mask = 1; mask <= full; mask++) {
int low = mask & -mask;
int rest = mask ^ low;
for (int sub = rest;; sub = (sub - 1) & rest) {
int s = sub | low;
if (sum[s] <= 4 && dp[mask ^ s] != INT_MAX)
dp[mask] = min(dp[mask], dp[mask ^ s] + 1);
if (sub == 0) break;
}
}
cout << dp[full] << "\n";
}
// Sub 2: tham lam theo so nguoi. O(n).
// - Nhom 4: 1 xe. Nhom 3: 1 xe, xe do con 1 cho cho nhom 1.
// - Nhom 2: hai nhom 2 chung 1 xe. Nhom 2 le: 1 xe, con 2 cho cho hai nhom 1.
// - Nhom 1 con lai: 4 nguoi / xe.
void sub2() {
long long c[5] = {0, 0, 0, 0, 0};
for (int x : a) c[x]++;
long long ans = c[4] + c[3];
long long ones = c[1];
ones -= min(ones, c[3]);
ans += c[2] / 2;
if (c[2] % 2 == 1) {
ans++;
ones -= min(ones, 2LL);
}
ans += (ones + 3) / 4;
cout << ans << "\n";
}
int main() {
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 17) sub1();
else sub2();
return 0;
}
Bình luận