- 正确答案：这是一个典型的贪心 + 二分搜索结合的优化问题。核心策略是：对每种糖果，其价格函数为分段常数函数（购买数量 ≤ k_i 时单价为 a_i，> k_i 时单价降为 b_i，且 b_i < a_i），目标是在总预算 m 下最大化购买糖果总数。最优解法是——先用二分搜索确定最大可能购买总数 x，再用贪心验证是否能在 m 元内买到至少 x 颗；验证过程对每种糖果计算买 t 颗的最小代价（t 可取 0 到 min(x, k_i + (x - k_i))，但更优的是：为凑满 x 颗，应优先用低价段（b_i）多买，但受限于高价段上限 k_i，因此每种糖果最多可用低价段买 (x - k_i) 颗（若 x > k_i），其余必须用高价段；实际验证时采用“反向贪心”：对每种糖果，计算买 1 颗的边际成本下界（即：若当前还没买够 k_i 颗，则第 1 颗成本为 a_i；但若已买 ≥k_i 颗，则后续每颗成本为 b_i）。更严谨高效的做法是：验证函数 feasible(x) 的实现为——将所有糖果按“从高价段切换到低价段的临界点”建模，等价于：对每种糖果 i，前 k_i 颗单价 a_i，之后无限颗单价 b_i。于是买 x 颗的最小花费 = 对所有糖果 i，分配 t_i 颗（∑t_i = x，t_i ≥ 0），使总成本 ∑[min(t_i, k_i)*a_i + max(0, t_i - k_i)*b_i] 最小。该分配问题可贪心求解：将每种糖果视为一个“成本递减序列”，其第 j 颗的成本为：j ≤ k_i 时为 a_i，j > k_i 时为 b_i。因此所有糖果的所有“单颗成本”可抽象为一个超大数组（共 sum_i(k_i + ?) 项），但我们无需显式构造。正确做法是：把每种糖果拆成两个虚拟“价格段”——高价段（长度 k_i，单价 a_i）和低价段（长度无穷，单价 b_i），然后全局按单价升序取前 x 颗。由于低价段单价 b_i 恒小于 a_i，所以最优策略一定是：优先买所有低价段中单价最低的那些颗，不够再买高价段中单价最低的。但注意：低价段的获取前提是已买满对应糖果的 k_i 颗高价段——不，这是误解！题设“价格随购买数量在两个数切换”意思是：对该糖果，无论你买多少颗，第 1 到第 k_i 颗单价为 a_i，第 (k_i+1) 颗起单价为 b_i ——即它是独立计数的，不是全局累计。因此每种糖果的采购是独立的，其成本函数 c_i(t) = t ≤ k_i ? t*a_i : k_i*a_i + (t−k_i)*b_i。于是总成本为 ∑c_i(t_i)，约束为 ∑t_i = x，t_i ∈ ℕ。这是一个凸分离优化问题，可用贪心（类似Huffman但带阈值）或堆模拟。最优验证算法是：使用最小堆，初始将每种糖果的“第 1 颗成本”入堆，即 a_i（因为 t_i=0→1 的增量成本为 a_i）；每次弹出最小成本，累加，并将该糖果的下一颗成本压入堆：若当前已买 t_i 颗，则第 (t_i+1) 颗成本为：若 t_i < k_i 则为 a_i，否则为 b_i。重复 x 次，累加总成本，与 m 比较。时间复杂度 O(x log n)，但 x 可达 1e9，不可行。因此必须换思路：用二分答案 + 数学验证。关键观察：c_i(t) 是分段线性凸函数（斜率从 a_i 降到 b_i），其反函数（给定花费，最多买多少颗）可解析计算。故 feasible(x) 应直接计算最小花费：对每个 i，c_i(t) 的逆函数 t_i(c) = min(k_i, floor(c/a_i)) 若 c ≤ k_i*a_i，否则 k_i + floor((c − k_i*a_i)/b_i)。但我们需要的是 ∑t_i = x 的最小 ∑c_i，这等价于在总花费 C 下最大化 ∑t_i(C)，而 t_i(C) 如上，但 C 未知。正确高效解法是：二分总花费？不，题目给定 m，求最大 x。所以应二分 x（0 ~ m/b_min，b_min = min_i b_i），对每个候选 x，计算 min_cost(x) = min_{∑t_i=x} ∑c_i(t_i)。该 min_cost(x) 可用贪心+堆在 O(n log n + x log n) 算出，但 x 太大。必须数学化解析。注意到：最优分配必满足“边际成本相等”原则——即对任意两种糖果 i,j，若 t_i > 0 且 t_j < ∞，则第 t_i 颗 i 的成本 ≤ 第 (t_j+1) 颗 j 的成本。由于每种糖果的边际成本序列是非增的（a_i, a_i, ..., a_i, b_i, b_i, ...），整个系统的边际成本序列是所有糖果的这些序列的归并。因此 min_cost(x) 就是该归并序列前 x 项之和。而归并序列的结构可被压缩表示：有 n 个高价段（各长 k_i，值 a_i）和 n 个低价段（各无限长，值 b_i）。于是前 x 项和 = 所有高价段贡献 + 所有低价段贡献。具体地，设我们取了 h_i ∈ [0,k_i] 颗高价段糖果 i，和 l_i ≥ 0 颗低价段糖果 i，满足 ∑(h_i + l_i) = x，且对每个 i，若 l_i > 0 则 h_i = k_i（因低价段只能在高价段买完后才启用）。因此 l_i > 0 ⇒ h_i = k_i，故 h_i ∈ [0,k_i]，l_i ≥ 0，且 h_i < k_i ⇒ l_i = 0。于是总颗数 x = ∑h_i + ∑l_i，其中 l_i > 0 仅当 h_i = k_i。令 S = {i | h_i = k_i}，则 ∑h_i = ∑_{i∈S} k_i + ∑_{i∉S} h_i，且 ∑l_i = x − ∑h_i。总成本 = ∑_{i∈S} (k_i*a_i + l_i*b_i) + ∑_{i∉S} h_i*a_i = ∑_i k_i*a_i * I(i∈S) + ∑_{i∉S} h_i*a_i + ∑_{i∈S} l_i*b_i。为最小化此式，在 S 固定时，应让 h_i 对 i∉S 尽量小（即 0），因为 a_i > 0；同时 l_i 应全分配给 b_i 最小的那些 i∈S。因此最优策略是：选定一个集合 S，买满所有 i∈S 的高价段（k_i 颗），再用剩余预算买低价段中 b_i 最小的糖果。但 x 是总颗数，不是预算。所以重新建模：为达到总颗数 x，必须至少买满某些糖果的高价段。令 K = ∑k_i。若 x ≤ K，则所有糖果都只用高价段，此时 min_cost = min sum of x smallest a_i's —— 即选 x 种糖果（可重复？不，每种可买多颗，但 a_i 相同），所以是取最小的 a_i，买 x 颗？错：每种糖果 i 的前 k_i 颗都是 a_i，所以若 x ≤ K，最优是选 a_i 最小的那个糖果，买 min(x, k_i) 颗？不，可以混合：因为所有高价段单价 a_i，所以买 x 颗的最小花费就是 x 乘以全局最小 a_i？不对！例如糖果1：k1=1, a1=10；糖果2：k2=100, a2=5；x=2：买糖果2的2颗花10元；若只买糖果1的1颗+糖果2的1颗，花10+5=15>10。所以最优是全部集中买 a_i 最小且 k_i 足够大的糖果。因此 x ≤ K 时，min_cost(x) = min over i of { if x ≤ k_i then x*a_i else +∞ }？不，可以跨糖果：因为所有高价段单价 a_i，问题退化为“有 n 个物品，物品 i 可提供最多 k_i 个单位，每个单位成本 a_i，求买 x 单位最小成本”，这是经典贪心：按 a_i 升序排序，依次取，直到凑够 x。所以 min_cost(x) for x≤K = 前缀和：sort candies by a_i, then sum_{j=1 to p-1} k_{i_j}*a_{i_j} + r*a_{i_p} where r = x − sum_{j=1 to p-1} k_{i_j}。同理，x > K 时，必须用低价段。总高价段容量为 K，所以至少需用低价段 x−K 颗。低价段中，糖果 i 的单价为 b_i，且无数量限制（只要其高价段已买满），所以低价段整体可看作：有 n 个供应源，源 i 的单价 b_i，供应量无限，但启用源 i 的固定成本是 k_i*a_i（即必须先付这笔钱才能开始用 b_i）。因此 min_cost(x) = min over all subsets S⊆[n] of { sum_{i∈S} k_i*a_i + min_cost_low(x − sum_{i∈S} k_i) }，其中 min_cost_low(y) 是用 S 中糖果的低价段买 y 颗的最小成本 = y * min_{i∈S} b_i（因可全用最便宜的 b_i）。所以 min_cost(x) = min_{S} { sum_{i∈S} k_i*a_i + (x − sum_{i∈S} k_i) * min_{i∈S} b_i }，约束 sum_{i∈S} k_i ≤ x。令 T = sum_{i∈S} k_i，则表达式为 sum_{i∈S} k_i*a_i + (x−T)*b_S，其中 b_S = min_{i∈S} b_i。注意 sum k_i*a_i ≥ T * min_{i∈S} a_i，但无法简化。最终高效算法是：枚举哪个糖果提供最低 b_i（即设 b_min = min_i b_i，且设 I* = argmin b_i），则最优 S 必包含 I*（否则可用 I* 替换 S 中某元素降低 b_S）。因此只需考虑 S 包含 I* 的情况。进一步，对每个可能的 b_val = b_i，令 S_b = {i | b_i = b_val}，则最优 S 是某个 S_b 的子集且含 I*。但更简单：固定最低 b_i 的值 b0，然后对每个 i 满足 b_i = b0，计算若强制用糖果 i 的低价段（即 i∈S），则 min_cost(x) = k_i*a_i + (x−k_i)*b0 + min over other j of {0 or k_j*a_j − k_j*b0}？不。标准解法是：将每种糖果 i 视为一个函数 f_i(t) = c_i(t)，则 min_cost(x) = (f_1 □ f_2 □ ... □ f_n)(x)，其中 □ 是infimal convolution。而每个 f_i 是凸分段线性，故其infimal convolution也是凸分段线性，断点仅出现在 t = k_i 处。因此 min_cost(x) 的分段点集合是 {0, k_{i1}, k_{i1}+k_{i2}, ..., K, K+1, K+2, ...}，但数量仍大。实践中的最优解是：二分 x，用堆模拟前 x 颗的最小边际成本（O(x log n)），但 x 上界为 m / min(b_i, min a_i) ≤ 1e9，不可行。因此必须用数学方法：注意到 min_cost(x) 是凸函数，其差分（边际成本）是非减的？不，是分段常数且非增的（因 a_i > b_i，所以每种糖果的边际成本从 a_i 降到 b_i）。整个系统的边际成本序列是非增的，所以 min_cost(x) 是凹函数？不，c_i(t) 是凸的（二阶差分≥0），infimal convolution保持凸性，所以 min_cost(x) 是凸函数，其一阶差分（边际成本）是非减的。验证：c_i(t) 的边际成本序列是 [a_i, a_i, ..., a_i (k_i times), b_i, b_i, ...]，a_i > b_i，所以是非增的。infimal convolution of non-increasing sequences is non-increasing? No — infimal convolution corresponds to sorting and summing, so the merged marginal cost sequence is the sorted (ascending) order of all individual marginal costs. Since each c_i has marginal costs [a_i (k_i times), b_i (inf times)] and a_i > b_i, the smallest marginal costs are all the b_i's, then larger ones are a_i's. So the global marginal cost sequence is non-decreasing? Let's sort all marginal costs in ascending order: first all b_i's (repeated infinitely), then all a_i's. But b_i < a_i, so yes — the smallest possible marginal cost is min b_i, then next is min of remaining b_i's or same b_i, etc., and only after exhausting all b_i options (but they're infinite) do we touch a_i. This is wrong: because to get a b_i marginal cost for candy i, you must have already bought k_i pieces at a_i, so there's a setup cost. Therefore the effective marginal cost for the first piece of candy i is a_i, not b_i. So the global sequence of achievable marginal costs is: all a_i's (each appears k_i times), then all b_i's (each appears infinitely). When sorted ascending, it's: sort all a_i's and b_i's together, but with multiplicity: a_i has count k_i, b_i has count ∞. Since b_i < a_i, all b_i entries come before all a_i entries in the sorted list. But b_i entries are infinite, so the first infinitely many marginal costs are min b_i. That can't be — you can't get min b_i on the first piece. The key is: the marginal cost of the j-th piece of candy i is: if j ≤ k_i then a_i else b_i. So to get a piece with marginal cost b_i, you must have already allocated k_i pieces to candy i. So the system has dependencies. Therefore the correct greedy is: use a min-heap of tuples (marginal_cost, candy_id, current_count), initialized with (a_i, i, 1) for all i. Pop min, add to total cost, then push next marginal cost for that candy: if current_count < k_i then (a_i, i, current_count+1) else (b_i, i, current_count+1). After x pops, total cost is min_cost(x). This is O(x log n) per feasibility check, and x up to 1e9 makes binary search over x impossible. Hence the intended solution is different: re-read problem — “每种糖果的价格随购买数量在两个数切换”，典型描述是：买第1颗a_i，第2颗a_i，...，第k_i颗a_i，第(k_i+1)颗b_i，第(k_i+2)颗b_i，...。所以 c_i(t) = t*a_i if t≤k_i else k_i*a_i + (t−k_i)*b_i。这是一个凸函数。现在，给定总预算 m，求 max x s.t. min_cost(x) ≤ m。由于 min_cost(x) 是凸的（逐段线性，斜率非减？计算斜率变化：c_i'(t) = a_i for tk_i, and at t=k_i the right-derivative is b_i < a_i = left-derivative, so c_i is concave at k_i? No, convexity requires epigraph convex, and c_i is convex because its second difference is non-negative: c_i(t+1)+c_i(t−1)−2c_i(t) = 0 for tk_i+1, and at t=k_i: c_i(k_i+1)+c_i(k_i−1)−2c_i(k_i) = [k_i*a_i+b_i] + [(k_i−1)*a_i] − 2*[k_i*a_i] = b_i − a_i < 0 → concave! So c_i is concave at the kink. Actually c_i is piecewise linear with decreasing slope (a_i then b_i < a_i), so it's concave. Therefore min_cost(x) = min sum c_i(t_i) is concave (sum of concave is concave), so its maximum under linear constraint is at extreme points — but we want max x s.t. min_cost(x) ≤ m, and min_cost(x) is increasing and concave, so it grows slower than linear. Thus binary search on x is valid, and we need an O(n log n) or O(n) feasibility test. The heap method is O(x log n), too slow. Better method: note that for large x, almost all pieces are bought at some b_i, so the dominant cost is x * b_min, plus fixed cost from k_i*a_i − k_i*b_min for candies used. Specifically, min_cost(x) = x * b_min + sum_{i} max(0, k_i*a_i − k_i*b_min − ???). Standard solution in programming contests is: sort candies by b_i, then for each prefix of candies with b_i ≤ current threshold, compute cost. But known efficient solution is: let’s define for each candy i, the “savings” of using its低价段 instead of paying a_i for all: each piece beyond k_i saves (a_i − b_i). So to buy x pieces, minimum cost = x * b_min + sum over i of max(0, k_i * (a_i − b_min) − adjustment). Actually, the optimal strategy is: choose one candy i* with minimal b_i, buy as many as possible from its低价段, but to do that, must first buy k_i* pieces at a_i*. Then remaining budget can buy more at b_i*. But other candies may offer better a_i for the initial k_i. So optimal is: select candy i to be the “base” for低价段, pay k_i*a_i to unlock b_i, then spend rest on b_i. So min_cost(x) = min over i of { k_i*a_i + max(0, x − k_i) * b_i }? No, because you can use multiple candies'低价段. For example, two candies: i1: k1=1,a1=10,b1=1; i2: k2=1,a2=10,b2=2; x=3. Then option1: use i1 as base: pay 10 + 2*1 = 12; option2: use i2: 10 + 2*2 = 14; but better: buy 1 from i1 at a1=10, 1 from i2 at a2=10, 1 from i1 at b1=1 → total 21? No, that's 10+10+1=21 > 12. Or buy 1 from i1 (a1), 2 from i1 (b1): 10+1+1=12. So single-base is sufficient? Proof: suppose optimal uses two bases i and j. Then cost includes k_i*a_i + k_j*a_j + (x−k_i−k_j)*b_min. But if we instead use only i as base and buy all extra at b_i = b_min, cost is k_i*a_i + (x−k_i)*b_min ≤ k_i*a_i + k_j*a_j + (x−k_i−k_j)*b_min because k_j*a_j ≥ k_j*b_min. So single-base is always at least as good. Therefore min_cost(x) = min over i of { k_i*a_i + max(0, x − k_i) * b_i }. This is O(n) per check! Then binary search x from 0 to m//min_b + max_k, about O(n log(m)). This is the intended solution. - 解答思路：首先准确理解题意——每种糖果i有一个阈值k_i，购买前k_i颗单价为a_i，超过k_i颗后，后续每颗单价降为b_i（b_i < a_i）。目标是在总预算m下，最大化总购买颗数x。关键洞察是：最优策略必定是“选定某一种糖果i作为低价段主力”，即先买满其k_i颗（花费k_i*a_i），然后剩余颗数全部以b_i单价购买（因为b_i是全局最小单价，否则可替换为b_min对应的糖果获得更低成本）。因此，对每个候选糖果i，买x颗的最小可能花费为：若x ≤ k_i，则x*a_i；若x > k_i，则k_i*a_i + (x−k_i)*b_i。遍历所有i，取这些花费的最小值，即得min_cost(x)。然后在x∈[0, X_max]上二分搜索，其中X_max = m // min_b + max_k（保守上界），对每个mid，计算min_cost(mid)，若≤m则可行，右移；否则左移。最终返回最大可行x。 - 深度知识讲解：本题考察对贪心策略存在性的证明能力、凸/凹函数性质理解、以及二分答案的经典范式。底层知识点包括：1）分段线性成本函数的infimal convolution性质；2）为何“单基准”策略最优——源于b_i < a_i导致跨糖果混合使用高价段不优于集中使用一个低价段源；3）二分答案的适用条件：单调性（x增大 ⇒ min_cost(x)非减）和可行性验证的高效性（O(n)）；4）边界处理：x的上界估计需考虑最坏单价min_b，且初始阈值k_i的影响。该模型广泛应用于资源采购、云计算实例预留（如AWS Reserved Instances：预付固定费解锁更低按量单价）、供应链批量折扣等场景。 - 伪代码： function solve(n, m, candies): // candies[i] = (a_i, b_i, k_i) b_min = min(candies[i].b for i in [0,n)) X_max = m // b_min + max(candies[i].k for i in [0,n)) + 10 lo, hi = 0, X_max while lo < hi: mid = (lo + hi + 1) // 2 if feasible(mid, m, candies): lo = mid else: hi = mid - 1 return lo function feasible(x, m, candies): if x == 0: return true min_cost = infinity for each candy in candies: a, b, k = candy.a, candy.b, candy.k if x <= k: cost = x * a else: cost = k * a + (x - k) * b min_cost = min(min_cost, cost) return min_cost <= m

文远知行暑期-AI infra 一面分享

全站热榜

创作者周榜