Bỏ qua đến nội dung

Hướng giải: KTHSUM

KTHSUM

Mã bài: free015 Nhóm: Uncategorized Điểm: 100 điểm
Giới hạn
1,0 s, 256 MB
Tỉ lệ AC
8,2%
Người giải
3
Chỉ đọc hướng giải khi bế tắc và đừng sao chép mã trong đó. Hãy tôn trọng người ra đề và người viết hướng giải: nộp lời giải chính thức khi chưa tự giải được bài có thể khiến bạn bị khóa tài khoản.

Nguồn: Free Contest

Subtask 1

Vì n \le 1000 nên ta có thể sinh toàn bộ n^2 phần tử của dãy D, sắp xếp theo thứ tự không giảm rồi in ra k phần tử đầu.

Độ phức tạp: O(n^2.log(n^2))

Subtask 2

Thay vì sinh toàn bộ n^2 phần tử, ta chỉ sinh k phần tử nhỏ nhất của dãy D bằng cách sử dụng heap hoặc set như sau:

  • Sắp xếp dãy B theo thứ tự không giảm.
  • Với mỗi phần tử a_i của dãy A, thêm vào heap/set cặp phần tử (a_i, b_1).
  • Thực hiện thao tác sau k lần: Lấy ra cặp phần tử (a_i, b_j) có tổng nhỏ nhất từ heap/set và in ra tổng đó. Thêm vào heap/set cặp phần tử (a_i, b_{j+1}) nếu j < n.

Độ phức tạp: O((n + k).log(n))

Bình luận