Bài gợi ý: Câu 3. Hộp quà (HSG 9 - Quảng Trị 2025-2026)

Tóm tắt: Chia dãy \(n\) phần tử thành hai đoạn. Đoạn đầu lấy \(K\) phần tử. Đoạn sau lấy các phần tử còn lại. Tìm \(K\) lớn nhất sao cho ghép được \(K\) cặp thỏa mãn phần tử bên trái nhỏ hơn phần tử bên phải.

Xét ví dụ với 10 hộp quà có giá trị 2 1 4 2 3 2 4 5 2 3. Nếu thử chọn \(K = 4\), ta lấy 4 phần tử đầu là 2 1 4 2 làm hộp thứ nhất. Các phần tử còn lại từ vị trí thứ 5 trở đi làm hộp thứ hai.

Ta cần kiểm tra xem \(K\) phần tử đầu có thể ghép đôi với \(K\) phần tử sau hay không. Mỗi phần tử bên trái phải nhỏ hơn phần tử bên phải được ghép cùng.

Nếu duyệt qua mọi giá trị của \(K\) từ 1 đến \(n\), ta sẽ mất rất nhiều thời gian. Với \(n \le 10^5\), cách kiểm tra trực tiếp từng \(K\) sẽ làm chương trình chạy quá chậm.

Nhận thấy rằng nếu chọn được \(K\) giỏ quà, ta thường cũng ghép được với số lượng nhỏ hơn. Tính chất đơn điệu này cho phép ta dùng chặt nhị phân, là kỹ thuật thu hẹp khoảng tìm kiếm giá trị \(K\) bằng cách chia đôi liên tục.

Để kiểm tra một giá trị \(K\) có hợp lý không, ta áp dụng chiến lược tham lam bằng cách sắp xếp tăng dần các phần tử của cả hai nhóm. Ta ghép phần tử nhỏ nhất của nhóm trái với phần tử nhỏ nhất có thể ở nhóm phải sao cho thỏa mãn điều kiện giá trị.

Trong quá trình cài đặt, ta dùng std::sort để sắp xếp hai đoạn và dùng hai con trỏ để duyệt qua từng phần tử. Khi cần thử một giá trị giữa, gọi hàm check(mid) để đếm số cặp ghép được rồi điều chỉnh biên trái và biên phải.