szawinis's blog

Need help with problem from TOI (Thailand Olympiad in Informatics)
By szawinis, history, 9 years ago, In English

Problem Statement (story changed so it's easier to understand): The are N problems and M programmers. The ith programmer (1 <= i <= M) can complete the task in ti minutes. Each programmer solves on problem at time. What is the shortest time required for all the programmers to finish all of their tasks?

Example:

Input: N = 5, M = 2, t1 = 7, t2 = 12

Output: 24

Any suggestions? Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

Do binary search on time.For a specific time T,the ith programmer can solve T/ti problem,in that way you can check whether the time is enough to solve N problems in O(M).the total time is O(Mlogt).Sorry for my bad English.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you very much. The problem was much simpler than I thought ;)

→ Reply