LaFolle's blog

Queue
By LaFolle, 12 years ago, In English

I solved it using sorting + dp. In tags it is 'binary search' + 'sorting'. Couldn't think of binary search solution.

BTW, size limit is 10^6 and not 10^5.

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First of all I think it will be better to write to link and not only problem name (maybe I'm wrong, but I do not know how to search problems by name).

Here is the link (I think you are talking about): 101C Queue.

Maybe I'm looking on different problem, but tags I see are: "constructive algorithms", "greedy", "sortings" and limit (for h_i) in this problem is 10^9.

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For each position on the queue calculate the youngest person from that position to the end. You can do binary search to find the farthest place on the queue such that this min is less than the age of the current walrus, which is the position of the farthest walrus that is younger than the i-th one.

→ Reply