货币系统详细题解

问题描述

在网友的国度中共有 $n$ 种不同面额的货币，第 $i$ 种货币的面额为 $a[i]$，每种货币都有无穷多张。货币系统记作 $(n,a)$。两个货币系统等价当且仅当它们能表示的非负整数金额完全相同。现需找到与原货币系统等价且货币种数 $m$ 最小的系统，求最小 $m$。

算法思路

核心在于筛选出「必要货币」—— 即无法被其他货币组合表示的货币。具体步骤：

1. 排序处理：将货币面额从小到大排序，确保较小面额先被处理（小面额可能是大面额的组成基础）。
2. 动态规划标记可表示金额：用布尔数组 $F$ 标记已能表示的金额（$F[x] = true$ 表示金额 $x$ 可被当前筛选出的货币表示）。
3. 筛选冗余货币：对每个面额，若其已能被之前的货币表示（$F[A[i]] = true$），则为冗余货币，不计入结果；否则为必要货币，并用其更新 $F$ 数组，标记更多可表示的金额。

代码解析

#include <bits/stdc++.h>
using namespace std;
int t;
int main() {
    // freopen("money.in", "r", stdin);
    // freopen("money.out", "w", stdout);
    cin >> t;  // 读取测试组数

    while (t--) {
        int n;
        cin >> n;  // 货币种数
        int A[n + 1];  // 存储货币面额
        bool F[25001] = {true};  // F[x]标记金额x是否可被表示，初始F[0]=true（0元可表示）

        for (int i = 1; i <= n; i++) {
            cin >> A[i];  // 读取面额
        }

        sort(A + 1, A + n + 1);  // 面额从小到大排序
        int ans = n;  // 初始假设所有货币都是必要的

        for (int i = 1; i <= n; i++) {
            // 若当前货币已能被之前的货币表示，则为冗余货币
            if (F[A[i]]) {
                ans--;
            } else {
                // 用当前货币更新可表示的金额
                for (int j = A[i]; j <= A[n]; j++) {
                    F[j] |= F[j - A[i]];  // 若j-A[i]可表示，则j可表示
                }
            }
        }

        cout << ans << endl;  // 输出必要货币的数量
    }
    return 0;
}

关键逻辑说明

1. 排序的作用：从小到大处理货币，确保判断某货币是否冗余时，所有可能组成它的小面额货币已被考虑。
2. F数组的意义：$F[x]$ 为 $true$ 表示金额 $x$ 可被当前保留的必要货币组合表示。初始时仅 $F[0] = true$（0元无需任何货币即可表示）。
3. 冗余判断：对于排序后的第 $i$ 个货币 $A[i]$，若 $F[A[i]] = true$，说明它可被之前的货币表示，是冗余的，减少结果计数；否则，用它更新 $F$ 数组，标记所有能通过它扩展的可表示金额。

样例分析

第一组数据

• 输入：$n=4$，面额 $[3,19,10,6]$
• 排序后：$[3,6,10,19]$
• 处理过程：
  • $A[1]=3$：$F[3]$ 初始为 $false$（非冗余），用3更新 $F$，标记 $3,6,9,\dots$ 可表示。
  • $A[2]=6$：$F[6]$ 已为 $true$（可被3表示），冗余，$ans=4-1=3$。
  • $A[3]=10$：$F[10]$ 为 $false$（非冗余），用10更新 $F$，标记 $10,13(10+3),16(10+6),\dots$ 可表示。
  • $A[4]=19$：$F[19]$ 为 $true$（$19=3×3+10×1$），冗余，$ans=3-1=2$。
• 输出：$2$

第二组数据

• 输入：$n=5$，面额 $[11,29,13,19,17]$
• 排序后：$[11,13,17,19,29]$
• 处理过程：每个货币均无法被之前的货币表示（如13不能被11表示，17不能被11+13表示等），均为必要货币。
• 输出：$5$

复杂度分析

• 时间复杂度：每组数据中，排序为 $O(n\log n)$；遍历货币并更新 $F$ 数组的总复杂度为 $O(n \times a_{\text{max}})$（$a_{\text{max}}$ 为最大面额）。整体为 $O(T \times (n\log n + n \times a_{\text{max}}))$。
• 空间复杂度：$O(a_{\text{max}})$，主要为 $F$ 数组的空间（大小为最大面额 $2.5 \times 10^4$）。

算法标签

• 动态规划
• 贪心算法
• 货币系统优化
• 冗余元素筛选

数据范围

• 全部数据：$1 \le T \le 20$，$n,a[i] \ge 1$
• 测试点 $1\sim 3$：$n=2$，$a[i] \le 10^3$
• 测试点 $4\sim 6$：$n=3$
• 测试点 $7\sim 8$：$n=4$
• 测试点 $9\sim 10$：$n=5$
• 测试点 $11\sim 13$：$n \le 13$，$a[i] \le 16$
• 测试点 $14\sim 16$：$n \le 25$，$a[i] \le 40$
• 测试点 $17\sim 20$：$n \le 100$，$a[i] \le 2.5 \times 10^4$