Bình luận

• 
  

  -1

  cl_dsonnd    10:25 p.m. 19 Tháng 8, 2024

  thi non qua, ko biet lam bai 4

• 
  

  0

  lamdeptrai    10:26 p.m. 19 Tháng 8, 2024 ← đã chỉnh sửa →

  chỉ bài cuối đi

• 
  

  -2

  cl_dsonnd    10:59 p.m. 19 Tháng 8, 2024

  Thuật toán điền nước vào các khóa trong hồ bơi
  Để bắt đầu, chúng ta sẽ chỉ mở một số đầu ống ứng vì cần điền đủ nước vào tất cả các khóa, và nhiều ống bên trái ảnh hưởng đến tổng dung tích của các bể, điều này rõ ràng là có lợi ích. Hãy liệt kê số ống nước mà chúng ta sẽ mở, cụ thể là đầu ống nào sẽ được mở và tính toán dpi - thời gian cần thiết để điền đầy các khóa đầu tiên nếu mở tất cả các ống đầu tiên. Hãy giới thiệu một mảng hỗ trợ prefix - tổng dung tích của các cửa ở đầu i. Sau đó dpi=max(dpi-1, ⌈pref_i/i⌉). Hãy xem vì sao như vậy. Chúng ta cần điền nước vào tất cả các cửa ải trước đó i−1 và cũng cần để cửa thứ i được điền. Lưu ý rằng nếu cửa thứ i không có đủ thời gian để được điền vào thời gian dpi−1, thì nó sẽ được điền vào thời gian ⌈prefi/i⌉ (việc điền sẽ xảy ra vào thời gian prefi/i, nhưng vì trong điều kiện yêu cầu của chúng ta đề cập đến các thời gian số nguyên, chúng ta có thể làm tròn lên và không sử dụng toán học thực), điều quan trọng là khi nước cần thiết được đổ vào tất cả các khóa chung từ tất cả các ống nước. Bây giờ, khi đã biết dpi cho tất cả các ống đang mở, ta có thể tính toán tương tự để xác định thời gian khi tất cả n cửa ải được đầy đủ. Đối với i này sẽ là max(dpi, ⌈prefn/i⌉). Dĩ nhiên rằng khi mở một ống nước bổ sung, thời gian sẽ không tăng thêm, vì vậy chúng ta có thể thực hiện tìm kiếm nhị phân theo thời gian và xác định câu trả lời cho yêu cầu mong muốn. Nếu yêu cầu t bé hơn thời gian điền chưa tối thiểu cho tất cả các khóa (khi tất cả các ống nước đều mở), thì cần in -1. Tổng thời gian chạy O(n+qlog(n)).
  Cre: https://codeforces.com/blog/entry/103978
  dịch: Chatgpt

• 
  

  0

  quangadhc    12:06 p.m. 22 Tháng 8, 2024

  :orz:

• 
  

  1

  Yuki    8:07 p.m. 20 Tháng 8, 2024

  ghe vay sao

• 
  

  0

  anhquan24    10:57 a.m. 20 Tháng 8, 2024

  anh sơn ko lim khiếp =)

• 
  

  -2

  tugnthanh2    9:54 a.m. 20 Tháng 8, 2024

  vãi cả chưởng, thằng sơn
19 bình luận nữa