Bài 4: Xây tháp (XT.*) - Đề KĐCL HSG xã Đô Lương 2025-2026(chỉnh sửa ND) Bạn Phùng được cử lên chơi 1 trò chơi của hoạt động "Ngày hội STEM" ở Trường THCS Lý Nhật Quang. Trò chơi như sau:

• Cho các viên gạch được đánh số. Mỗi số trên viên gách tượng trưng cho "Độ bền" của chúng.
• Một viên gạch chỉ có thể xếp số lượng gạch nhỏ hơn hoặc bằng "Độ bền" của nó.
• Các thí sinh được cho các viên gạch như nhau. Mục tiêu là xếp một tháp cao nhất bằng số gạch đã cho.
• BTC sẽ công nhận người xếp được số tầng nhiều nhất. Mỗi tầng chỉ có 1 viên gạch duy nhất Bạn Phùng muốn thắng trò chơi này. Hãy giúp bạn Phùng tìm được cách xếp có số tầng cao nhất. In/Out:
• Input: Nhập từ File XT.INP
• Một số nguyên n là số gạch được cho.(1<=n<=2*10^5)
• Dãy phần tử a1,a2,a3,....,an là độ bền của mỗi viên gạch.(0<=ai<n)</li>
• Output: In ra File XT.OUT một số nguyên dương là số tầng cao nhất Phùng có thể xếp được. Ví dụ: XT.INP: 5 4 3 2 1 0 XT.OUT: 5

Hướng dẫn giải:

1. Ý tưởng cốt lõi Khi duyệt qua mảng đã sắp xếp giảm dần, ta giả định tháp có thể xây được tối đa đến hết mảng. Tuy nhiên, mỗi viên gạch a[i] tại vị trí i sẽ tự đặt ra một cái "trần nhà" (giới hạn chiều cao) cho toàn bộ cái tháp dựa vào sức gánh của nó.
2. Các bước thực hiện Bước 1: Sắp xếp:Sắp xếp mảng độ bền a theo thứ tự giảm dần (viên khỏe nhất nằm đầu). Bước 2: Khởi tạo: Khai báo biến range = INT_MAX (hoặc dùng hằng số INF = 1e9 + 7) để làm cái trần nhà vô hạn ban đầu. Bước 3: Duyệt và lấy Min tuyến tính: Chạy vòng lặp for từ i = 0 đến n - 1. Cập nhật range = min(range, a[i] + i + 1).

Kết quả cuối cùng của bài toán chính là min(range, n) (để phòng trường hợp tất cả các viên gạch đều quá khỏe và gánh được nhiều hơn cả tổng số lượng gạch n đang có).