3 ms·
Seems like there is a rust priority queue (https://doc.rust-lang.org/std/collections/binary_heap/index.html https://doc.rust-lang.org/std/collections/binary_hea
by floxy 2y ago
Seems like there is a rust priority queue (https://doc.rust-lang.org/std/collections/binary_heap/index.html https://doc.rust-lang.org/std/collections/binary_heap/index....). Would be interesting to see a version where you pop off the two smallest values, and push the sum back, until there is only one element left.
- aardvark179 2y agoThat works just great if your numbers are positive, but if they are both positive and negative, and in almost but not quite equal pairings it will fail to give the best answer even if you prioritise by magnitude.
- deleted 2y ago[deleted]
- recursive 2y agoIf it works for positives, then you can add all the positives in one bin, add all the negatives in one bin, and finish off with a single subtraction.
- anonymoushn 2y agoThat isn't a great method, see here: https://en.wikipedia.org/wiki/Catastrophic_cancellation https://en.wikipedia.org/wiki/Catastrophic_cancellation I wonder what methods give good results for this sort of input though.