1045. The Ice Cream You Can Afford

A stall lists n items with their prices. You have a budget and want to buy as MANY items as possible; what they cost in total does not matter beyond fitting the budget. Each item may be bought at most once.

Print the largest number of items you can buy.

budget 7, prices 1 3 2 4 1 -> 4 1 + 1 + 2 + 3 budget 7, prices 10 6 8 7 -> 1 budget 0, prices 1 -> 0

## What most people try first

This looks like a knapsack, and it is, with every item's value equal to 1. A table over the budget answers it, and the budget here reaches 10^14, so that table is not representable, let alone fillable.

Trying every subset is 2^n with n at 100000.

## Sort ascending and buy until you cannot

sort the prices, smallest first count = 0 for each price p: if budget < p: stop budget -= p count += 1

## Why the cheapest first is optimal

Suppose some optimal purchase buys k items. Sort those k prices; their total is at most the budget. Now compare them item by item with the k cheapest prices in the whole list. The jth cheapest overall is at most the jth cheapest of any particular set of k, so the k cheapest cost no more in total than the optimal purchase, and therefore also fit the budget.

So whenever k items are affordable at all, the k cheapest are affordable. The sorted prefix that fits is therefore the longest affordable set, which is what the sweep finds.

## Why stopping is right, not skipping

When a price does not fit, every later price is at least as large, so nothing after it fits either. Continuing the loop is harmless but pointless; what is NOT harmless is skipping an unaffordable item and continuing to buy, because on a sorted list that can never succeed and it hides the bug from you on unsorted input.

## Where this sits

Problem #611 hands out biscuits to children with appetites and is the two-list version of the same sorted walk. Problem #1071 also sorts and sweeps, but the total there is weighted by position, so a prefix of the sorted order is no longer the answer and the sweep has to stop for a completely different reason.

## Overflow

The budget reaches 10^14, so it must be read into a 64 bit integer: 10^14 is roughly fifty thousand times the signed 32 bit limit of 2147483647. A single price fits in 32 bits, which is why a half-converted solution passes most tests.

## Cost

Time O(n log n). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ budget ≤ 100000000000000` - `1 ≤ price[i] ≤ 1000000000`