Độ cứng

Nguồn: CLUE OJ – Chương 14: Cửa sổ trượt + Tham lam Độ khó: Dễ Tham lam Sắp xếp

Đề bài

Nam có $n$ viên gạch được đánh số từ 1 đến $n$. Các viên gạch có độ cứng lần lượt là $a_1, a_2, \ldots, a_n$. Một viên gạch có độ cứng $x$ nghĩa là Nam có thể chồng lên trên viên gạch đó tối đa $x$ viên gạch khác, nếu chồng nhiều hơn thì viên gạch đó sẽ bị vỡ.

Yêu cầu: Nam có thể sắp được chồng gạch cao nhất là bao nhiêu?

Dữ liệu vào: từ file tile.inp gồm:

• Dòng đầu tiên là số nguyên $n$ $(1 \le n \le 10^5)$ là số viên gạch.
• Dòng tiếp theo gồm $n$ số nguyên $a_1, a_2, \ldots, a_n$ $(0 \le a_i \le 10^9)$.

Kết quả: ghi ra file tile.out một số nguyên là kết quả của bài toán.

Ràng buộc: 60% số test ứng với $n \le 10^3$; 40% số test còn lại không có ràng buộc gì thêm.

Ví dụ 1 – input

3
1 2 1

Ví dụ 1 – output

3

Ví dụ 2 – input

6
0 0 0 0 0 0

Ví dụ 2 – output

1

Giải thích: ví dụ 1 xếp được cả 3 viên: viên cứng 2 ở dưới cùng (chịu 2 viên), hai viên cứng 1 lần lượt ở giữa (chịu 1 viên) và trên cùng (chịu 0 viên). Ví dụ 2 mọi viên đều có độ cứng 0 – không chịu nổi viên nào, nên chồng chỉ cao 1 viên.

Lưu ý: đề gốc đọc/ghi file tile.inp / tile.out. Code bên dưới dùng if (fopen("tile.inp", "r")) { freopen(...); }: có file thì đọc file, không có thì đọc bàn phím.

Lời mở đầu

Bài toán xếp gạch này là một ví dụ rất "chuẩn" của tham lam + sắp xếp: viên nào yếu thì cho lên trên, viên nào cứng thì để dưới. Nghe thì hiển nhiên, nhưng cần biết khi nào bỏ một viên và vì sao bỏ như vậy là đúng. Mình đi từ cách vét cạn cho test nhỏ, tới tham lam $O(n^2)$ và cuối cùng là sắp xếp $O(n \log n)$.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

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ưởngYếu lên trênCách 1Vét cạn 2ⁿCách 2Tham lam O(n²)Cách 3Sắp xếp

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

Bộ test có 100 test, đúng như ràng buộc của đề: 60 test đầu có $n \le 10^3$, 40 test cuối $n = 10^5$. Chi tiết hơn:

Test	Số test	n	aᵢ	Đáp án	Số test có viên độ cứng 0
1 – 30	30	3 … 15	0 … 20	1 … 15	15
31 – 60	30	1 000 … 1 000	0 … 999 969 921	854 … 894	30
61 – 100	40	100 000 … 100 000	0 … 999 998 182	65 290 … 65 938	40

• Test 1, 2 chính là 2 ví dụ của đề. Test 1 – 30 rất nhỏ ($n \le 15$, $a_i \le 20$); có 24/30 test xếp được tất cả các viên.
• Test 31 – 60: $n = 1000$, $a_i$ tới gần $10^9$ – nhưng vẫn có nhiều viên độ cứng nhỏ nên đáp án chỉ khoảng 850 – 900.
• Test 61 – 100: $n = 10^5$, đáp án khoảng $6{,}5 \cdot 10^4$ – tức khoảng 1/3 số viên bị bỏ.

Subtask	Điều kiện	Test	Cách ăn được
1 (60%)	n ≤ 10³	1 – 60	Cách 2, 3 (Cách 1 chỉ ăn test 1 – 30, n ≤ 15)
2 (40%)	n ≤ 10⁵	61 – 100	Cách 3

Ý tưởngXây từ trên xuống, viên yếu lên trước

Trong một chồng cao $h$, đánh số vị trí từ trên xuống $0, 1, \ldots, h - 1$: viên ở vị trí $j$ có đúng $j$ viên đè lên, nên cần độ cứng $\ge j$. Vị trí càng thấp càng đòi hỏi cao.

Tham lam

Sắp xếp độ cứng tăng dần. Xây chồng từ trên xuống, biến cao = số viên đã có. Xét lần lượt từng viên: nếu $a_i \ge$ cao thì nó chịu được cả chồng hiện tại → đặt xuống dưới cùng, cao++; ngược lại thì viên này quá yếu, bỏ.

Vì sao đúng?

• Viên bị bỏ có $a_i <$ cao: nó không thể đứng ở vị trí cao trở xuống. Còn các vị trí phía trên đã có những viên yếu hơn hoặc bằng nó đứng rồi – đổi nó vào thay một viên ở trên cũng không làm chồng cao thêm. Bỏ nó không thiệt gì.
• Viên được nhận là viên yếu nhất còn dùng được cho vị trí hiện tại. Giữ các viên cứng hơn cho những vị trí thấp hơn (đòi hỏi cao hơn) là lựa chọn không bao giờ kém hơn.

Em nhập độ cứng các viên rồi bấm Tiếp để xem chồng gạch được xây từ trên xuống. Số nhỏ bên phải mỗi viên là số viên đang đè lên nó:

Độ cứng các viên

Ví dụ nhanh:

Cách 1Vét cạn mọi tập gạch – O(2ⁿ · n log n)

Thử mọi tập con các viên gạch. Một tập xếp được thành chồng khi và chỉ khi: sắp xếp tăng dần thành $b_0 \le b_1 \le \ldots$ thì $b_j \ge j$ với mọi $j$ (viên yếu thứ $j$ đặt ở vị trí $j$ tính từ trên). Tập lớn nhất thoả mãn là đáp án.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi tập con, kiểm tra tập bằng cách sắp xếp tăng dần.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Khung này giới hạn n ≤ 4 (2⁴ = 16 tập) để số bước không quá dài.

1. Điều kiện kiểm tra tập dùng luôn ý "viên yếu lên trên": nếu cách xếp tăng dần mà còn vỡ thì không cách xếp nào khác cứu được.
2. Có $2^n$ tập, nên chỉ chạy được khi $n$ khoảng 20 trở xuống.

Không gian$O(n)$

Thời gian$O(2^n \cdot n \log n)$

Kết quả chạy thật: C++ đúng 30/100 test (test 1–30, chậm nhất 0.012 giây); test 31–100 bị quá thời gian. Python đúng 30/100 test (test 1–30, chậm nhất 0.108 giây); test 31–100 bị quá thời gian.

Cách 2Tham lam, mỗi lần tìm viên phù hợp – O(n²)

Cài đặt trực tiếp tham lam mà chưa sắp xếp: mỗi lần duyệt cả mảng tìm viên yếu nhất trong các viên chịu được cao viên, đặt nó xuống dưới chồng. Không còn viên nào chịu được thì dừng.

C++▶ Chạy tay từng dòng codeCách 2: mỗi lần chọn viên yếu nhất còn chịu được cả chồng.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Ô đỏ: viên quá yếu so với chồng hiện tại · ô mờ: viên đã xếp · ô xanh: viên đang được chọn.

1. Điều kiện a[i] >= cao lọc các viên chịu nổi; trong số đó chọn a[i] nhỏ nhất.
2. Mỗi vòng while tốn $O(n)$, chồng cao tối đa $n$ → $O(n^2)$: ổn với $n = 10^3$, quá chậm với $n = 10^5$.

Không gian$O(n)$

Thời gian$O(n^2)$

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

Cách 3Sắp xếp + duyệt một lượt – O(n log n)

Sắp xếp tăng dần thì "viên yếu nhất còn chịu được" chính là viên kế tiếp trong mảng thoả $a_i \ge$ cao. Một vòng for là xong.

C++▶ Chạy tay từng dòng codeCách 3: sắp xếp tăng dần, viên nào chịu được cả chồng thì đặt xuống dưới.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Độ cứng tới $10^9$, mình để long long cho thoải mái (int cũng đủ).
2. Viên có độ cứng 0 vẫn luôn được nhận khi cao = 0 – nên đáp án luôn $\ge 1$ (đúng ví dụ 2).

Không gian$O(n)$

Thời gian$O(n \log n)$

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

Ghi chú của mình: cách 3 (C++) đúng 100/100 test, chậm nhất 0.022 giây; bản Python cách 3 cũng đúng hết, chậm nhất 0.101 giây. Bài này "hiền" ở chỗ chỉ cần nghĩ đúng thứ tự xếp: viên yếu ở trên, gặp viên quá yếu thì bỏ.

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 😇