Taxi

Nguồn: CLUE OJ – Chương 14: Cửa sổ trượt + Tham lam Độ khó: Dễ Tham lam Đếm phân phối

Đề bài

Để chúc mừng sinh nhật bạn Nhuận ngày 29/2, các bạn học sinh lớp 11A dự định tổ chức dã ngoại đến biển Nha Trang và lớp sẽ đi bằng taxi.

Các bạn trong lớp được chia thành $n$ nhóm, mỗi nhóm thứ $i$ gồm $s_i$ bạn $(1 \le s_i \le 4)$ và mỗi chiếc taxi chở tối đa 4 hành khách.

Vậy lớp 11A cần thuê ít nhất bao nhiêu chiếc taxi để chở các nhóm đi, với điều kiện là các bạn trong nhóm phải ngồi chung taxi (một taxi có thể chở một nhóm trở lên).

Dữ liệu nhập:

• Dòng đầu chứa số nguyên $n$ $(1 \le n \le 10^5)$ – số lượng các nhóm học sinh.
• Dòng thứ 2 chứa dãy số nguyên $s_1, s_2, \ldots, s_n$ $(1 \le s_i \le 4)$, cách nhau bởi dấu cách, với $s_i$ là số trẻ em trong nhóm thứ $i$.

Dữ liệu xuất: in 1 số nguyên duy nhất – số lượng tối thiểu taxi cần thiết để chở tất cả trẻ em đến nơi.

Giới hạn thời gian: 1 giây. Giới hạn bộ nhớ: 128 MB.

Ví dụ 1 – input

5
1 2 4 3 3

Ví dụ 1 – output

4

Ví dụ 2 – input

8
2 3 4 4 2 1 3 1

Ví dụ 2 – output

5

Giải thích ví dụ 1: các bạn có thể sắp xếp như sau: nhóm thứ 3 gồm 4 học sinh; nhóm thứ 4 gồm 3 học sinh; nhóm thứ 5 gồm 3 học sinh; nhóm thứ nhất và nhóm thứ 2 gồm 3 học sinh (1 và 2 học sinh). Vậy dữ liệu ra là 4.

Lời mở đầu

Đây là bài Taxi kinh điển (Codeforces 158B), một trong những bài tham lam đầu tiên mà bạn nào học thuật toán cũng gặp. Vì mỗi nhóm chỉ có 1 – 4 bạn nên thay vì quan tâm thứ tự các nhóm, ta chỉ cần đếm có bao nhiêu nhóm mỗi loại rồi ghép xe cho khéo. Mình sẽ giải bằng cách "mô phỏng xếp xe" trước, rồi rút gọn thành vài phép tính $O(n)$.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngGhép tham lamCách 1Mô phỏng xếp xeCách 2Đếm O(n)

Bộ testBộ test chính thức có gì?

Bộ test có 100 test, đề không ghi subtask nhưng chia đều 5 mức, mỗi mức 20 test:

Test	n	Đáp án	Lẻ 1 nhóm 2 bạn	Nhóm 1 bạn nhiều hơn nhóm 3 bạn
1 – 20	1 … 20	1 … 16	11/20	12/20
21 – 40	100 … 100	60 … 70	10/20	7/20
41 – 60	1 000 … 1 000	608 … 642	11/20	14/20
61 – 80	10 000 … 10 000	6 205 … 6 307	11/20	10/20
81 – 100	100 000 … 100 000	62 371 … 62 699	13/20	11/20

• Test 1 – 20 rất nhỏ, có cả test $n = 1$; 7 test thiếu hẳn một loại nhóm (vd không có nhóm 1 bạn) – bắt lỗi trừ ra số âm.
• Hai trường hợp dễ sai (số nhóm 2 bạn lẻ, và bạn lẻ còn dư sau khi ghép với nhóm 3) xuất hiện đều ở mọi mức. Hai ví dụ của đề không nằm trong bộ test.

Mức	Điều kiện	Test	Cách ăn được
1	n ≤ 20	1 – 20	Cách 1, 2
2	n = 100	21 – 40	Cách 1, 2
3	n = 10³	41 – 60	Cách 1, 2
4	n = 10⁴	61 – 80	Cách 1, 2
5	n = 10⁵	81 – 100	Cách 2

Ý tưởngGhép nhóm lớn trước, nhóm 1 bạn lấp chỗ trống

Gọi $c_1, c_2, c_3, c_4$ là số nhóm có 1, 2, 3, 4 bạn. Ta ghép xe theo thứ tự từ nhóm đông tới nhóm ít:

1. Nhóm 4 bạn: kín xe, không ghép được với ai → $c_4$ xe.
2. Nhóm 3 bạn: mỗi nhóm một xe (2 nhóm 3 bạn không ngồi chung được), xe còn đúng 1 chỗ → chở kèm 1 nhóm 1 bạn nếu còn. Thêm $c_3$ xe, $c_1$ giảm đi $\min(c_1, c_3)$.
3. Nhóm 2 bạn: cứ 2 nhóm ghép 1 xe → $\lfloor c_2 / 2 \rfloor$ xe. Nếu lẻ 1 nhóm thì nó đi 1 xe và chở kèm tối đa 2 bạn lẻ.
4. Nhóm 1 bạn còn lại: 4 bạn một xe → $\lceil c_1 / 4 \rceil$ xe.

Vì sao tham lam này tối ưu? Nhóm 4 và nhóm 3 thì chắc chắn mỗi nhóm cần riêng một xe (hai nhóm 3 bạn, hay 3 + 2, đều quá 4). Chỗ trống duy nhất cạnh nhóm 3 bạn chỉ vừa một nhóm 1 bạn, nên dùng nhóm 1 lấp vào là không phí. Sau đó chỉ còn nhóm 2 và nhóm 1: xếp hai nhóm 2 vào một xe là kín chỗ; phần lẻ thì nhóm 1 lấp nốt. Không có chỗ ngồi nào bị bỏ phí một cách "tránh được".

Em nhập số bạn của các nhóm rồi bấm Tiếp để xem từng loại nhóm được xếp lên xe:

Số bạn các nhóm

Ví dụ nhanh:

Cách 1Mô phỏng xếp xe – O(n · k)

Cách tự nhiên nhất: sắp xếp các nhóm giảm dần, rồi lần lượt cho mỗi nhóm lên xe đầu tiên còn đủ chỗ; không có xe nào đủ chỗ thì gọi xe mới. Thứ tự giảm dần đảm bảo các nhóm lớn được xếp trước, nhóm nhỏ đi lấp chỗ trống – đúng như ý tưởng ở trên.

Xem code C++ / Python – Cách 1: Mô phỏng xếp xe – O(n · k)

#include <bits/stdc++.h>
using namespace std;

int n, s[100005], con[100005];               // con[t] = số chỗ còn trống của taxi t

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) cin >> s[i];
    sort(s, s + n, greater<int>());          // nhóm đông xếp trước
    int k = 0;                               // số taxi đã gọi
    for(int i = 0; i < n; i++){
        int t = 0;
        while(t < k && con[t] < s[i]) t++;   // taxi đầu tiên còn đủ chỗ
        if(t == k) con[k++] = 4;             // không có → gọi taxi mới
        con[t] -= s[i];
    }
    cout << k;
    return 0;
}

import sys
def main():
    d = sys.stdin.read().split()
    n = int(d[0]); s = sorted(map(int, d[1:n + 1]), reverse=True)
    con = []
    for x in s:
        t = 0
        while t < len(con) and con[t] < x:
            t += 1
        if t == len(con):
            con.append(4)
        con[t] -= x
    print(len(con))
main()

C++▶ Chạy tay từng dòng codeCách 1: sắp xếp giảm dần, mỗi nhóm lên xe đầu tiên còn đủ chỗ.

Dữ liệu vào (stdin) – sửa thoải mái5 1 2 4 3 3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. con[t] là số chỗ trống của xe thứ $t$; vòng while tìm xe đầu tiên có con[t] >= s[i].
2. Không sắp xếp giảm dần là sai: ví dụ 1 1 3 3 xếp theo thứ tự đề thì hai bạn lẻ ngồi chung một xe, hai nhóm 3 bạn phải đi 2 xe riêng → 3 xe, trong khi đáp án là 2. Chạy thật bản không sắp xếp: 26/100 test đúng.
3. Mỗi nhóm có thể phải dò qua rất nhiều xe đã đầy (nhất là các xe chở nhóm 4 bạn) → tệ nhất $O(n^2)$.

Không gian$O(n)$

Thời gian$O(n \log n + n \cdot k)$, $k$ là số xe

Kết quả chạy thật: C++ đúng 80/100 test (test 1–80, chậm nhất 0.033 giây); test 81–100 bị quá thời gian. Python đúng 60/100 test (test 1–60, chậm nhất 0.058 giây); test 61–100 bị quá thời gian.

Cách 2Đếm rồi tính – O(n)

Không cần biết nhóm nào ở xe nào, chỉ cần đếm $c_1..c_4$ rồi làm 4 bước của ý tưởng.

Xem code C++ / Python – Cách 2: Đếm rồi tính – O(n)

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, c[5] = {0};                       // c[x] = số nhóm có x bạn
    cin >> n;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        c[x]++;
    }
    int ans = c[4];                          // nhóm 4 đi riêng
    ans += c[3];                             // nhóm 3 mỗi nhóm 1 xe...
    c[1] = max(0, c[1] - c[3]);              // ...chở kèm 1 bạn lẻ
    ans += c[2] / 2;                         // 2 nhóm 2 ghép 1 xe
    if(c[2] % 2 == 1){                       // dư 1 nhóm 2: chở kèm tối đa 2 bạn lẻ
        ans++;
        c[1] = max(0, c[1] - 2);
    }
    ans += (c[1] + 3) / 4;                   // bạn lẻ còn lại: 4 bạn 1 xe
    cout << ans;
    return 0;
}

import sys
def main():
    d = sys.stdin.read().split()
    n = int(d[0]); c = [0] * 5
    for x in d[1:n + 1]:
        c[int(x)] += 1
    ans = c[4] + c[3]
    c[1] = max(0, c[1] - c[3])
    ans += c[2] // 2
    if c[2] % 2 == 1:
        ans += 1
        c[1] = max(0, c[1] - 2)
    ans += (c[1] + 3) // 4
    print(ans)
main()

C++▶ Chạy tay từng dòng codeCách 2: đếm số nhóm mỗi loại rồi ghép xe bằng công thức.

Dữ liệu vào (stdin) – sửa thoải mái8 2 3 4 4 2 1 3 1

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. max(0, c[1] - c[3]): nếu số bạn lẻ ít hơn số nhóm 3 thì bạn lẻ hết sạch, không âm.
2. (c[1] + 3) / 4 là cách viết làm tròn lên $\lceil c_1 / 4 \rceil$ chỉ bằng số nguyên.

Không gian$O(1)$

Thời gian$O(n)$

Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất chỉ 0.010 giây. Python đúng 100/100 test, test chậm nhất chỉ 0.048 giây.

Ghi chú của mình: cách 2 (C++) đúng 100/100 test, chậm nhất 0.010 giây; bản Python cũng đúng hết, chậm nhất 0.048 giây. Bài này rất hay để luyện thói quen "đếm thay vì duyệt": giá trị nhỏ (1 – 4) thì đếm số lần xuất hiện là đủ.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇