题目背景 * 有 n 种武器，m 个材料 * 每个材料原本适配某个武器，可以花费一定代价修改为适配其他武器 * 目标：让适配武器1的材料数量 严格大于 其他所有武器 * 求解：最小总花费 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码逐段解析 1. 数据结构定义 变量 含义 作用 a[i] 武器 i 的材料花费数组 排序后贪心选最小花费 cnt[i] 武器 i 的当前材料数 判断是否满足条件 idx[i] 武器 i 的贪心指针 避免重复选择同一材料 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2. 输入与预处理 目的：排序后，a[i][0] 就是武器 i 最便宜的可修改材料，方便贪心选择。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3. 主循环：贪心转移 终止条件：cnt[1] > max(cnt[2], cnt[3], ..., cnt[n]) 贪心策略：每次选花费最小的材料从其他武器转移到武器1。 转移效果： * 武器1：+1 * 其他武器 pos：-1 * 一增一减，相对优势 +2，效率最高！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4. 输出结果 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 算法正确性证明 为什么贪心选最小花费是最优的？ 核心观察：每次转移操作的效果是固定的： * 武器1的材料数 +1 * 某个其他武器的材料数 -1 * 总花费 = 该材料的修改代价 贪心选择性质： * 假设存在最优解，其中某次转移选了花费 c1 的材料 * 如果存在更便宜的材料 c2 < c1 可选 * 用 c2 替换 c1，操作效果相同，但总花费更小 * 矛盾！所以最优解必然每次选最小花费 无后效性： * 每次转移只影响两个武器的计数 * 不影响其他材料的花费 * 局部最优 → 全局最优 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 复杂度分析 步骤 时间复杂度 说明 输入 + 排序 O(mlog⁡m)O(m \log m)O(mlogm) 每个材料排序一次 主循环 O(m×n)O(m \times n)O(m×n) 最多转移 mmm 次，每次遍历 nnn 个武器 总计 O(mlog⁡m+mn)O(m \log m + mn)O(mlogm+mn) n,m≤1000n,m \le 1000n,m≤1000 时完全可行 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 样例模拟 输入： 初始状态： 第1轮循环： * 检查：cnt[1]=1, mx=max(2,2)=2, 1>2? ❌ * 找最小：a[2][0]=5, a[3][0]=3 → 选武器3，花费3 * 转移：res=3, cnt[3]=1, cnt[1]=2, idx[3]=1 第2轮循环： * 检查：cnt[1]=2, mx=max(2,1)=2, 2>2? ❌（需要严格大于） * 找最小：a[2][0]=5, a[3][1]=7 → 选武器2，花费5 * 转移：res=8, cnt[2]=1, cnt[1]=3, idx[2]=1 第3轮循环： * 检查：cnt[1]=3, mx=max(1,1)=1, 3>1? ✅ * 退出循环，输出 8 验证：最终 cnt=[3,1,1]，武器1严格大于其他，总花费 3+5=8 ✓ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 注意事项 1. idx 数组的作用：避免重复选择同一材料，确保每个材料最多被转移一次 2. pos == -1 的判断：处理无解情况（其他武器材料都用完了还不满足条件） 3. long long 的使用：花费可能很大，防止溢出 4. 严格大于：条件是 cnt[1] > mx，不是 >= ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 对于 n≤1000n \le 1000n≤1000，当前 O(mn)O(mn)O(mn) 的写法已经足够高效。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 总结 1. 每次选择花费最小的材料，从其他武器转移到武器1 2. 直到武器1的材料数严格大于所有其他武器 3. 时间复杂度 O(mlog⁡m+mn)O(m \log m + mn)O(mlogm+mn)，空间复杂度 O(m+n)O(m + n)O(m+n)