- 正确答案：这是一个典型的动态规划问题，也称为“受限数字组合的最大值”或“数位DP的变种”，但更准确地说，若集合A中的元素是单个数字（如A={1,3,5}），且要求用A中的数字拼接成一个十进制整数（每位只能取自A），使得该整数 ≤ n 且尽可能大，则最优策略是贪心+回溯（或数位DP）；若A中是任意正整数（如A={2,7,15}），且允许重复使用、求若干个A中元素之和 ≤ n 的最大可能和，则为“完全背包问题”的变种（最大化价值且不超过容量，价值=重量=数值），此时目标是 max{sum of selected elements} s.t. sum ≤ n。由于题干未明确“组成”的定义，需分两种主流语义解析。校园招聘中高频考察的是后者（即子集和/背包类）和前者（数位构造类）。我们以更常见、更具区分度的**数位构造型**（A为数字集合，如A={0,1,3,5}，n=321，要求用A中数字构成一个≤321的最大整数，允许前导零？不允许？——通常不允许前导零，且位数可少于n）作为主解，并补充背包型解法。综合判断，本题最可能意图是：给定正整数n（如字符串或整数形式）和数字集合A（如A={1,3,5,7}），每个位置只能填A中的某个数字，构造一个十进制整数x，满足x ≤ n，且x在所有合法x中最大。这是经典的“构造最大≤n的数”问题，核心方法是：贪心尝试高位匹配，遇阻则降位回退+填最大可用数字。 - 解答思路： 1. 将n转为字符串s，长度为L。 2. 首先尝试构造L位数：从高位i=0开始，对每一位尝试填A中≤s[i]的最大数字a。 - 若存在a == s[i]，则填a，继续下一位； - 若存在a < s[i]，则填该a，后续所有位均填A中最大数字（贪心保证整体最大），构造完成； - 若不存在a ≤ s[i]（即A中最小数字都 > s[i]），则需退位：将已确定的前缀减1（模拟借位），再填充剩余位为A中最大数字；若前缀已为空（即首位无法选≤s[0]的数），则答案必为L−1位最大数（即|A|个max(A)拼接）。 3. 同时计算L−1位最大可能数（即len=L−1，每位填max(A)），与上述L位构造结果比较，取较大者。关键难点在于“退位”处理：例如n=200，A={1,9}，首位不能选≤'2'的数？可以选'1'或'9'，但'9'>'2'不行，'1'<'2'可行→填'1'，后面全填'9'→得199。但若n=100，A={0,1}，首位选'1'→继续；第二位s[1]='0'，A中≤'0'的只有'0'→填'0'；第三位s[2]='0'，同样填'0'→得100。若A={1}（无0），则n=100时，首位'1'可选，但第二位需≤'0'，A中无≤'0'的数字（'1'>'0'），此时必须退位：前缀"1"减1 → "0"无效（不允许前导零），故放弃3位数，直接取2位最大数："11"。因此完整流程： - Step 1：预处理A_digit = sorted([int(c) for c in A])，max_d = max(A_digit) - Step 2：尝试构造L位数： - res = [] - for i in range(L): candidate = [d for d in A_digit if d <= int(s[i])] if not candidate: break # 当前位无合法数字，需退位 if max(candidate) < int(s[i]): res.append(max(candidate)) res.extend([max_d] * (L - i - 1)) break else: # max(candidate) == int(s[i]) res.append(int(s[i])) - else: # 成功填满L位 → res就是n本身（当n所有位都在A中） return int(''.join(map(str, res))) - Step 3：若中途break（因candidate为空或选择小于s[i]后填充完毕），检查是否已构造res： - 若res长度 < L：说明成功构造了一个L位< n的数，返回int(''.join(...)) - 若因candidate为空中断：需退位。令 prefix = res[:-1]，然后对prefix执行“减1并保持每位∈A”的操作（类似大数减法），再补后缀。但更简单做法是：直接构造L−1位最大数 = int(str(max_d) * (L-1))，前提是L>1；若L==1，则答案为max{d∈A | d<=n}。但退位逻辑复杂，标准解法采用DFS+记忆化（数位DP）或迭代贪心+回溯。更鲁棒的做法是： - 先尝试构造L位：用数组ans[0..L-1]，初始None。 - i=0 to L-1: let limit = int(s[i]) try digit d from min(A_digit) to max(A_digit) descending order: if d > limit: continue if d < limit: then ans[i]=d, and ans[i+1..]=max_d → return this number if d == limit: ans[i]=d, continue to i+1 if no d <= limit: break - if broke at i: then answer is (L-1)-digit number: str(max_d)*(L-1) if L>1 else max{d∈A_digit | d<=n} - 深度知识讲解：本题本质是“带约束的字典序最大构造”，考点覆盖：（1）贪心算法的适用性与失效边界：高位优先填最大可能值，但必须保证后续可完成。此处“可完成”指存在一种填法使整个数≤n。当某位只能填 1) if L > 1: candidate_short = int(str(max_d) * (L - 1)) return candidate_short else: // L == 1: just pick max digit <= n return max([d for d in digits if d <= n]) if digits else 0 // Example: n=321, A={'1','3','5'} → digits=[1,3,5], max_d=5 // i=0: limit=3, candidate=3 → append 3 // i=1: limit=2, digits≤2: only 1 → 1<2 → append 1, then [5,5] → 315 // return 315 注意：上述伪代码未处理退位到更短位数的情况（如n=100, A={1}，需返回11而非1），因其本质是当L位无法构造时，L−1位也不一定可行（若max_d=1，L−1=2→11，但11<100，合法）。实际上，只要L−1≥1，str(max_d)*(L−1)一定≤n（因n有L位，最小L位数是10^(L−1)，而max_d*(L−1)位数最大为10^(L−1)−1）。故L−1位最大数恒合法。因此最终答案即为：max( L位构造结果（若存在）, (L−1)位最大数 )，而(L−1)位最大数恒存在（只要A非空且含非负数字）。

字节一面速挂

全站热榜

创作者周榜