SRM 679, D2, 250-Pointer (ListeningSongs)
James S. Plank
Tue Sep 13 22:54:52 EDT 2016
It's best to think about this problem in parts, solving each part before proceeding to the
Part 1: An album doesn't have T songs
This case is illustrated in example 6, but it comes from the constraints -- durations1
and durations2 can contain between 1 and 100 elements, and T will be between 1 and
100. There is nothing in the constraints that says that durations1.size() or
durations2.size() is ≥ T.
So test for this case first, and return -1 if either vector is too small. Test it on example
Part 2: You should to listen to the T shortest songs on each album
The best way to figure this out is to sort both vectors, and then sum up the first T
durations in both vectors.
If that number is too big, return -1. Otherwise, subtract the number from the
total number of seconds (you'll have to multiply minutes by 60). That's the
amount of time you have left after listening to T songs on each album.
Part 3: Of the remaining songs, listen to the shortest ones until you run out of time, or
you run out of songs
To do this, create a third vector. I called mine "FD" for "final durations." Create
this from the songs in the two vectors that are not in the first T songs of either
Now sort FD, and run through it, seeing if you can listen to each song. Return if
you can't listen to a song. If you finish FD, you're done -- you can listen to all
of the songs!
In sum, this program tripped up a lot of topcoders, but if you split it into parts, and use
the sort() method from the algorithms library, the solution is pretty straightforward.