贪心法-找零钱PTA

### 使用贪心算法解决找零钱问题

对于给定金额 \( x \)，将其转换成5分、2分和1分的硬币组合，要求每种硬币至少一枚。此问题可以通过遍历所有可能的情况来实现，而不是直接应用经典的贪心算法。然而，在某些情况下，贪心算法可以简化计算过程。

为了确保每种面额都至少有一个硬币，先分配一个5分、两个2分以及三个1分硬币作为基础配置[^1]。接着，剩余的钱数通过尽可能多地使用较大面值的硬币来进行兑换：

def change_coins(x):
    solutions = []
    
    for i in range((x - 3) // 5, 0, -1):  # 至少留出足够的空间放置其他两种类型的硬币
        remaining_after_five = x - 5 * i
        
        for j in range((remaining_after_five - 1) // 2, 0, -1):
            k = remaining_after_five - 2 * j
            
            if k >= 1 and i >= 1 and j >= 1:
                total_coins = i + j + k
                
                solution_string = f'fen5:{i}, fen2:{j}, fen1:{k}, total:{total_coins}'
                
                solutions.append(solution_string)

    return '\n'.join(solutions), len(solutions)


if __name__ == "__main__":
    amount = int(input().strip())
    result, count = change_coins(amount)
    print(result)
    print(f'count = {count}')

上述代码实现了对输入金额 `amount` 的处理逻辑，并按照指定格式输出结果。注意这里并没有严格遵循贪心策略，而是穷举了所有符合条件的可能性并进行了排序输出。