M29896: 购物

greedy, http://cs101.openjudge.cn/practice/29896/

你就要去购物了，现在你手上有 N 种不同面值的硬币，每种硬币有无限多个。为了方便购物，你希望带尽量少的硬币，但要能组合出 1 到 X 之间的任意值。

输入

第一行两个数 X, N，以下 N 个数，表示每种硬币的面值。

输出

最少需要携带的硬币个数，如果无解输出-1。

样例输入

20 4
1 2 5 10

样例输出

提示

N <= 10, X <= 10000 (tag:greedy)

来源

https://www.luogu.com.cn/problem/P1658(TA-hhy)

目标是：在给定若干种硬币面值（每种无限供应）的前提下，选出最少数量的硬币，使得它们的组合能够表示出从 1 到 X 的所有整数值。

如果无法做到（比如没有面值为 1 的硬币，那连 1 都凑不出来），就输出 -1。

首先只要有1面值就一定可以表示所有数字，如果没有1面值就一定表示不了1，因此只要判断面值中有没有1即可判断可行性. 然后从小到大逐个数判断，每当遇到无法表示的数 $i$ 时，只要添加一个不超过这个数的最大面值硬币 $j$ ，由于 $i - j$ 在之前就判断过可以表示，因此 $i$ 可以用 $(i - j) + j$ 表示出来，并且由于 $i - j \sim i - 1$ 都判断过可以表示，那么事实上 $i \sim i + j - 1$ 都可以表示了，由于 $j$ 是可选的最大硬币面值，因此这就是最佳方案.

这是一个典型的“覆盖连续区间”问题。可以维护一个当前能表示的最大连续值 max_reach（初始为 0），然后不断选择硬币来扩展这个范围。思路：

必须包含面值 1，否则无法组成 1 → 无解，输出 -1。
将硬币面值从小到大排序。
维护当前能组成的最大连续值 max_val（初始为 0）。
同时维护一个“候选池”：所有 ≤ max_val + 1 的硬币中，选最大的那个（因为加它能让 max_val 增加最多）。
- 但实际上，由于硬币可重复使用，更优策略是：
  每次在所有满足 coin <= max_val + 1 的硬币中，选择面值最大的，然后带一枚它，更新 max_val += coin，计数器 +1。
重复直到 max_val >= X。

但注意：因为硬币可以多次使用，其实我们可以多次使用同一个硬币来快速扩展。

python

def solve():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    X = int(data[0])
    N = int(data[1])
    coins = list(map(int, data[2:2+N]))
    
    # 去除大于 X 的硬币（无用）
    coins = [c for c in coins if c <= X]
    if not coins:
        if X == 0:
            return 0
        else:
            return -1
    
    # 排序
    coins.sort()
    
    # 必须要有 1，否则无法覆盖 1
    if coins[0] > 1:
        return -1
    
    max_reach = 0  # 当前能覆盖 [1, max_reach]
    count = 0      # 使用的硬币数量
    
    while max_reach < X:
        # 选择满足 coin <= max_reach + 1 的最大面值硬币
        candidate = -1
        for coin in coins:
            if coin <= max_reach + 1:
                candidate = coin
            else:
                break  # 因为已排序，后面的更大
        
        if candidate == -1:
            return -1  # 无法扩展
        
        max_reach += candidate
        count += 1
        
        if max_reach >= X:
            break
    
    return count

# 主程序
print(solve())

python

import bisect

def solve():
    X, N = map(int, input().split())
    coins = list(map(int, input().split()))
    coins.sort()
    
    # 如果最小面值 > 1，无法凑出 1
    if coins[0] > 1:
        print(-1)
        return

    reach = 0
    ans = 0

    # 可以重复使用同一个面值多次，所以不移除
    while reach < X:
        target = reach + 1
        # 找 coins 中最大且 <= target
        idx = bisect.bisect_right(coins, target) - 1
        if idx < 0:
            print(-1)
            return
        c = coins[idx]
        reach += c
        ans += 1

    print(ans)

if __name__ == "__main__":
    solve()

算法复杂度

先对面值排序：O(N log N)
每一步用二分查找找到最大 ≤ reach+1：O(log N)，循环次数等于答案（最多约 O(X/min_coin)），总体可接受（X ≤ 10000, N ≤ 10）。

M29896: 购物 ​

M29896: 购物