Nên mời những người bạn có mức e ngại nào?

Thoạt nhìn, việc được tùy ý chọn mức e ngại cho từng người bạn khiến bài toán có vẻ phức tạp. Tuy nhiên, mời toàn những người mức 0 luôn là tối ưu: họ đứng lên ngay lập tức, vì thế hỗ trợ được mọi khán giả có mức dương. Lập luận tham lam này đúng trong mọi tình huống: nếu một phương án dùng những người bạn có mức lớn hơn 0 giải được bài, ta có thể thay từng người bằng một người mức 0 mà phương án vẫn thành công.

Cần mời bao nhiêu người?

Để nhóm có mức \(k\) đứng lên, trước họ phải có ít nhất \(k\) người đã đứng. Những người này gồm khán giả có mức nhỏ hơn \(k\) và những người bạn mức 0 ta mời. Gọi \(t\) là số khán giả gốc đã đứng; khi xét mức \(k\), số bạn cần có ít nhất là

Vì cùng một nhóm bạn đã mời hỗ trợ mọi mức về sau, ta duyệt các mức tăng dần, tính yêu cầu ở từng mức và lấy giá trị lớn nhất. Giá trị lớn nhất đó chính là số bạn tối thiểu để mọi khán giả đứng dậy vỗ tay.

Dưới đây là cài đặt Python mẫu:

for tc in range(input()):
  smax, string = raw_input().split()
  t = 0
  min_invite = 0
  for k in range(int(smax) + 1):
    min_invite = max(min_invite, k - t)
    t += int(string[k])
  print "Case #%d: %d" % (tc + 1, min_invite)

Đầu vào đã sắp theo mức tăng dần nên chỉ cần duyệt chuỗi một lần. Vì min_invite khởi đầu bằng 0, không cần viết riêng \(\max(k-t,0)\): phép lấy max với giá trị hiện tại đã xử lý trường hợp âm. Độ phức tạp thời gian là \(O(S_{max})\) và bộ nhớ phụ \(O(1)\).

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2015 - Qualification Round - Standing Ovation, kho Google Coding Competitions (Apache-2.0).