[Buổi 13][Thiết kế tham lam][HW] Bài 1: Ghép hành khách vào cabin
Ghép hành khách vào cabin
Bối cảnh và bài toán
Có n hành khách, mỗi cabin chở tối đa hai người và tổng khối lượng không vượt x. Cần dùng ít cabin nhất.
Yêu cầu
Tìm số cabin tối thiểu.
Input
- Dòng 1:
n x. - Dòng 2:
nkhối lượng.
Output
In số cabin tối thiểu.
Ràng buộc
1 <= n <= 2 * 10^51 <= p[i] <= x <= 10^9
Chấm điểm
| Subtask | Điểm | Điều kiện | Official tests |
|---|---|---|---|
| S1 | 30% | n ≤ 500 | 01–03 |
| S2 | 30% | n ≤ 5 * 10^4 | 04–06 |
| S3 | 40% | Không có ràng buộc bổ sung | 07–10 |
Ví dụ 1
Input
4 10
7 2 3 9
Output
3
Giải thích. Có thể ghép 7 với3; 9 và2 đi riêng hoặc ghép 9 không với ai.
Ví dụ 2
Input
5 10
1 2 3 4 5
Output
3
Giải thích. Ghép 1+5, 2+4, còn3.
Thông tin bài tập
| Thuộc tính | Giá trị |
|---|---|
| Mã bài | DSA-M04-B13-HW01 |
| Buổi | B13 |
| Loại bài | HOMEWORK |
| Mức độ khó | Dễ (Easy) |
| Thời gian làm bài khuyến nghị | 30 phút |
| Time limit | 2 giây |
| Memory limit | 256 MB |
| Tổng điểm | 100 |
| Chuẩn ngôn ngữ tham chiếu | C++11 trở lên |
Nguồn: Phỏng theo CSES Problem Set — Ferris Wheel (Task 1090).
Tham khảo: https://cses.fi/problemset/task/1090
Comments