雪糕的最大数量 图解题解

固定现金，买最多支雪糕，返回什么

给一个价格数组 costs，costs[i] 是第 i 支雪糕的价格，再给一笔现金 coins。可以按任意顺序挑任意几支，只要总价不超过 coins，目标是买到的支数最多，返回这个最大支数。题面 costs=[1,3,2,4,1]、coins=7，答案是 4；换成 costs=[10,6,8,7,7,8]、coins=5，最便宜的一支都要 6 元，一支也买不起，答案是 0。

手里就这么点钱，先挑哪几支

现金是死的，雪糕价格参差不齐，能塞进预算的组合多到数不清。要是随手先抱一支贵的走，比如那支 4 元的，一下就吃掉大半现金，剩的钱只够再添一两支便宜货，同一笔钱花在贵雪糕上换回的支数就少。把所有子集都枚举一遍去比最多支数，n 一大就爆，得找个不试遍所有组合的挑法。

为什么先买最便宜的一批，支数一定最多

目标是支数最多，不是把钱押在哪一支上，那每一块钱就该尽量多换雪糕。把价格从小到大排好，从最便宜的一支起往贵里买，支数就顶到头了。可以这样说服自己：假设某种买法买到了最多的 k 支，里头却有一支比某支它没买的还贵，把这支贵的退掉、换成那支更便宜的没买雪糕，花的钱只减不增，支数仍是 k，方案照样合法。这种替换一路做下去，最省钱的 k 支永远落在全场最便宜的那 k 支上——从便宜到贵地买，绝不会比别的买法买得少。

排序之后，一支支怎么买、何时收手

排完序从最便宜那支起，每支只问一句：手里的现金够不够付它。只要现金大于等于当前价格 c，就买下它，现金扣掉 c、已买支数加一，接着看下一支更贵的。等碰到第一支付不起的——现金比它的价格还少——就当场停手，此刻已买的支数就是答案。为什么不再往后翻翻能不能捡个便宜？价格已经从小到大排好，这支是没买的里最便宜的一支，连它都付不起，后面更贵的一定也付不起。

[1,3,2,4,1] 排完序，7 元买到第几支

先把 [1,3,2,4,1] 排成 [1,1,2,3,4]，现金 7 元、已买 0 支。第一支 1 元，7≥1 买下，剩 6 元、1 支；第二支 1 元，6≥1 买下，剩 5 元、2 支；第三支 2 元，5≥2 买下，剩 3 元、3 支；第四支 3 元，3≥3 正好付得起、花光现金买下，现金归零、4 支。轮到第五支 4 元，手里一分不剩付不起，停手。买到的正是最便宜的前四支、恰好花掉 7 元，得到 4 支。

几个写错就少买的地方，和它到底多快

不排序直接贪、或从贵的买起，会白白挤掉本可以拿的便宜支，支数算少。判定得用现金大于等于价格，等号要取到——现金恰好等于价格时花光也能拿下这一支，写成严格大于就会在钱数刚够时误判成买不起，少算一支。遇到第一支买不起别再往后翻找，排序后更贵的不可能反而买得起。

总时间是 O(n log n)，n 是雪糕支数——最重的就是排序这一步，压过后面那趟从便宜到贵、每支一次比较一次扣钱的线性扫描。价格有明确上限时改用计数排序，能把排序压到线性、总体降到 O(n+max)，买雪糕的逻辑一个字不用改。空间上只用现金和计数两个变量，额外开销都来自排序本身。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        costs.sort()
        for i, c in enumerate(costs):
            if coins < c:
                return i
            coins -= c
        return len(costs)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        sort(costs.begin(), costs.end());
        int n = costs.size();
        for (int i = 0; i < n; ++i) {
            if (coins < costs[i]) return i;
            coins -= costs[i];
        }
        return n;
    }
};

Java

import java.util.*;
class Solution {
    public int maxIceCream(int[] costs, int coins) {
        Arrays.sort(costs);
        int n = costs.length;
        for (int i = 0; i < n; ++i) {
            if (coins < costs[i]) {
                return i;
            }
            coins -= costs[i];
        }
        return n;
    }
}