Bỏ qua đến nội dung

Hướng giải: CITY

CITY

Mã bài: free011 Nhóm: Uncategorized Điểm: 100 điểm
Giới hạn
1,0 s, 256 MB
Tỉ lệ AC
30,0%
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

Sắp xếp các mảnh đất theo thứ tự B_i - C_i giảm dần. Khi đó, với hai mảnh đất i < j, nếu ta xây dựng nhà hàng trên mảnh đất i và khu vui chơi trên mảnh đất j, ta có thể thay vào đó xây dựng khu vui chơi tại i và nhà hàng tại j và lợi nhuận sẽ không giảm.

Nói cách khác, trong lời giải tối ưu, tồn tại một số nguyên K sao cho:

  • Trong K mảnh đất đầu tiên, sẽ có Y khu vui chơi và K - Y trung tâm thương mại.
  • Trong các mảnh đất còn lại, sẽ có Z nhà hàng và X + Y - K trung tâm thương mại.

Giả sử A_i = 0 (nếu không, ta có thể biến đổi (A_i, B_i, C_i) thành (0, B_i - A_i, C_i - A_i) và cộng A_i vào đáp án). Khi đó, với một số nguyên K cố định, ta cần tính tổng của hai giá trị sau:

  • Tổng của Y giá trị lớn nhất trong các giá trị B_1, B_2, ..., B_K.
  • Tổng của Z giá trị lớn nhất trong các giá trị C_{K+1}, C_{K+2}, ..., C_{X+Y+Z}.

Việc tính toán các giá trị trên có thể được thực hiện bằng một hàng đợi ưu tiên.

Độ phức tạp: O((X+Y+Z).log(X+Y+Z))

Bình luận