Life Transfer#12803

Life Transfer (Editorial)

Author:

Eugenie Daniel Posdărascu

Developer:

Radu Vișan

Editorialist:

Adrian Budău

The easy approach to this problem is to fix the number of motorcycles to rent. The number of cars needed will be uniquely determined by this.

Now let's say we want cars and motorcycles. We need the oldest people to drive the cars, and the next oldest people to drive the motorcycles. For both of these groups we can divide the people into categories:

  • People that have at least years more than the minimum age required to drive the vehicle. From these people, we can afford to take years from each of them to give to someone else.

  • People that have the minimum age required to drive the vehicle, but they are less than years older than the minimum age required. From these people we can take years equal to their age out of which we subtract l_c or l_m respectively. This can be rewritten as the sum of their ages - l_c or l_m multiplied by their number.

  • People that do not have the minimum age required to drive the vehicle, but need less than or equal to years to reach it. This is symmetrical to the case above: they need years equal to l_p or l_m out of which we subtract the sum of their ages.

  • People that are more than years younger than the minimum required age to drive their vehicle. In this case, it means and can not represent the number of cars and motorcycles.

We can also divide the rest of the people in two categories:

  • People with age at least d+1 out of which we can take years to give to someone else (treated as the first category for cars/motorcycles)

  • People with age less than or equal to , out of which we can take years equal to their age minus 1 (treated as the second category for cars/motorcycles).

It can be seen that if we order all people by age all these categories of people become intervals which we can precompute for the whole array and then restrict depending on and . And the number of years we can take / we need to give become partial sums on this ordered array of years.

Total complexity: \mathcal{O}(n \log n) time and space.