Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

kmcc's blog

By kmcc, history, 3 months ago, In English,

The problem statement is as follows :

There are N hotels and M groups. For each hotel you know the number of free rooms. Your task is to assign hotel rooms for groups of tourists. All members of a group want to stay in the same hotel.

The groups will come to you one after another, and you know for each group the number of rooms it requires. You always assign a group to the first hotel that has enough rooms. After this, the number of free rooms in the hotel decreases.

1 <= N, M <= 10^5

Source

I can't come up with a better solution than a linear scan for each group. Please help.

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

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Edit: initially misunderstood task

this can be solved with a segment tree, that supports range maximum and setting value. Just put the hotels in order there, and binary search shortest prefix that contains a hotel with large enough capacity. This gives O(n log(n)^2). You can achieve O(n log(n)) by doing binary search on the segment tree itself: first check if the first half of the tree has a satisfactory hotel. If it does, go to the first half. Otherwise, go to the second half. Then repeat.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if i use multiset< pair<int, int> >(hotelSize, index)
    In this case the solution will fail
    1 9 8
    8
    The ans is 9 but lower_bound will give 8