In k phần tử nhỏ nhất bằng std::priority_queue
Khi chỉ cần vài giá trị nhỏ nhất của một tập dữ liệu, ta không phải sắp xếp toàn bộ mảng.
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Khi chỉ cần vài giá trị nhỏ nhất của một tập dữ liệu, ta không phải sắp xếp toàn bộ mảng. Hàng đợi ưu tiên luôn đặt phần tử được ưu tiên lên đầu, nên nếu đảo ngược tiêu chí so sánh thì phần tử nhỏ nhất sẽ luôn nằm sẵn ở đỉnh và ta chỉ việc lấy ra đúng k lần.
Yêu cầu
Cho một mảng gồm n số nguyên và một số nguyên k. Hãy in ra k phần tử nhỏ nhất của mảng theo thứ tự tăng dần, mỗi giá trị trên một dòng. Nếu một giá trị xuất hiện nhiều lần thì nó được tính nhiều lần trong dãy kết quả.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. Mỗi giá trị trên một dòng riêng, không in thêm chữ nào khác.
Input
- Dòng thứ nhất: số nguyên n là số phần tử (1 <= n <= 20).
- Dòng thứ hai: n số nguyên cách nhau bởi dấu cách (|giá trị| <= 10000).
- Dòng thứ ba: số nguyên k là số phần tử cần in (1 <= k <= 5, và k <= n).
Output
- In ra k dòng, mỗi dòng một giá trị, theo thứ tự tăng dần.
Ràng buộc
- 1 <= k <= 5, k <= n <= 20, |giá trị| <= 10000.
- Dãy kết quả có thể chứa giá trị lặp lại.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
5
9 1 8 2 7
3
Output
1
2
7
Ví dụ 2
Input
6
4 4 2 2 9 9
4
Output
2
2
4
4
Giải thích
Với dữ liệu vào:
Ba giá trị nhỏ nhất là 1, 2, 7, nên kết quả là:
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
