The correct way to do UVa 10954: Add All is to use a priority queue. At first, I thought I could keep all the integers to be added in a vector, sort the vector, and the minimum cost solution would always be that which added the next smallest number to the total. However, this is flawed reasoning because once the running total exceeds the sum of two numbers not included in the running total, adding another number to the running ceases to be the most cost-effective operation. Thus, my first solution using a sorted vector was WA. Next, I tried using a priority queue. Because we want to add the two smallest number available at any given step in order to minimize cost, the priority queue needs to be a min heap. The default implementation of the STL priority_queue is a max heap, so in order to get this to behave like a min heap, I multiplied all the integers by -1 before inserting them into the heap. Thus the smallest positive integers become the largest negative integers and have higher priority in the heap. After knowing this approach, the rest is simple simulation. Just donâ€™t forget to push the new sum back onto the heap!

# UVa 10954: Add All

*
For technical reasons, comments are temporarily unavailable on my posts.
If you'd like to discuss this article with me, feel
free to email me at
or hit me up on
Twitter.
*