以下是 LCP 47. 入场安检 的 Java 实现。题目分析- N 个安检室容量分别为 capacities[i]总和为 M。- 恰好 M1 位观众编号 0 M依次入场。- 每个安检室可选择两种类型之一- 先进先出队列最早进入的先离开- 后进先出栈最晚进入的先离开- 观众从 0 号安检室开始依次通过所有安检室。- 求有多少种设定安检室类型的方案使得编号 k 的观众第一个通过最后一个安检室。核心思路数学建模 → 01背包求方案数关键观察- 队列容量为 x 的队列第一个进入的人总是第一个出去的。它不会阻挡任何人。- 栈容量为 x 的栈当装满 x-1 人后再进入第 x 人时栈顶最后进入的人会被弹出。这意味着一个容量为 x 的栈实际上会延后 x-1 个人通过。为了让编号 k 的人第一个通过最后一个安检室需要恰好有 k 个人被延后。问题转化为 从 capacities 中选择若干安检室设为栈使得这些栈的 (容量 - 1) 之和恰好等于 k求方案数。这就是一个经典的 01背包求方案数 问题。Java 实现javaimport java.util.Arrays;class Solution {private static final int MOD 1_000_000_007;public int securityCheck(int[] capacities, int k) {// 01背包求方案数// f[j] 表示前 i 个安检室中选择若干栈其 (容量-1) 之和为 j 的方案数int[] f new int[k 1];Arrays.fill(f, 0);f[0] 1; // 什么都不选方案数为1for (int cap : capacities) {int w cap - 1; // 选栈则贡献 cap-1选队列则贡献 0不选// 倒序遍历01背包标准写法for (int j k; j w; j--) {f[j] (f[j] f[j - w]) % MOD;}}return f[k];}}复杂度分析- 时间复杂度O(N × K)其中 N capacities.lengthK k- 空间复杂度O(K)验证输入 输出 说明capacities [2,2,3], k 2 2 选容量2的栈(w1) 容量3的栈(w2)3≠2或选两个容量2的栈(w112) ✓或选容量3的栈(w2) ✓capacities [3,3], k 3 0 最大和为 224但无法凑出3capacities [4,3,2,2], k 6 2 两种方案下载完整代码[Solution_LCP47.java](sandbox:///mnt/agents/output/Solution_LCP47.java)
以下是 LCP 47. 入场安检 的 Java 实现。题目分析- N 个安检室容量分别为 capacities[i]总和为 M。- 恰好 M1 位观众编号 0 M依次入场。- 每个安检室可选择两种类型之一- 先进先出队列最早进入的先离开- 后进先出栈最晚进入的先离开- 观众从 0 号安检室开始依次通过所有安检室。- 求有多少种设定安检室类型的方案使得编号 k 的观众第一个通过最后一个安检室。核心思路数学建模 → 01背包求方案数关键观察- 队列容量为 x 的队列第一个进入的人总是第一个出去的。它不会阻挡任何人。- 栈容量为 x 的栈当装满 x-1 人后再进入第 x 人时栈顶最后进入的人会被弹出。这意味着一个容量为 x 的栈实际上会延后 x-1 个人通过。为了让编号 k 的人第一个通过最后一个安检室需要恰好有 k 个人被延后。问题转化为 从 capacities 中选择若干安检室设为栈使得这些栈的 (容量 - 1) 之和恰好等于 k求方案数。这就是一个经典的 01背包求方案数 问题。Java 实现javaimport java.util.Arrays;class Solution {private static final int MOD 1_000_000_007;public int securityCheck(int[] capacities, int k) {// 01背包求方案数// f[j] 表示前 i 个安检室中选择若干栈其 (容量-1) 之和为 j 的方案数int[] f new int[k 1];Arrays.fill(f, 0);f[0] 1; // 什么都不选方案数为1for (int cap : capacities) {int w cap - 1; // 选栈则贡献 cap-1选队列则贡献 0不选// 倒序遍历01背包标准写法for (int j k; j w; j--) {f[j] (f[j] f[j - w]) % MOD;}}return f[k];}}复杂度分析- 时间复杂度O(N × K)其中 N capacities.lengthK k- 空间复杂度O(K)验证输入 输出 说明capacities [2,2,3], k 2 2 选容量2的栈(w1) 容量3的栈(w2)3≠2或选两个容量2的栈(w112) ✓或选容量3的栈(w2) ✓capacities [3,3], k 3 0 最大和为 224但无法凑出3capacities [4,3,2,2], k 6 2 两种方案下载完整代码[Solution_LCP47.java](sandbox:///mnt/agents/output/Solution_LCP47.java)
