蓝桥杯【第14届省赛】Python B组 76_题目描述 有一根长度为 len 的横向的管道,该管道按照单位长度分为 len 段。 每一

【问题描述】

小蓝手中有 2023 种不同面值的硬币，这些硬币全部是新版硬币，其中第 i (1 ≤ i ≤ 2023) 种硬币的面值为 i ，数量也为 i 个。硬币兑换机可以进行硬币兑 换，兑换规则为：交给硬币兑换机两个新版硬币 coin1 和 coin2 ，硬币兑换机会 兑换成一个面值为 coin1 + coin2 的旧版硬币。

小蓝可以用自己已有的硬币进行任意次数兑换，假设最终小蓝手中有 K 种不同面值的硬币（只看面值，不看新旧）并且第 i (1 ≤ i ≤ K) 种硬币的个数为 。小蓝想要使得 的值达到最大，请你帮他计算 这个值最大是多少。

注意硬币兑换机只接受新版硬币进行兑换，并且兑换出的硬币全部是旧版硬币。

【解析及代码】

第一种思路是，根据面值 2023 的硬币数最多，直接尽可能地兑换面值 2023 的旧硬币，总数为：

上述方法在兑换时使用的最大面值为 (因为用 1011 和 1012 凑成 2023 时，数量取决于 1011，所以不考虑 1012)，最优的凑法是凑成面值 2023 (= 1011 × 2 + 1) 的旧硬币

第二种思路是， 枚举用于兑换的新硬币最大面值 ![r \in 1012, 2023)，并兑换面值为 的旧硬币，此时用于兑换的新硬币的最小面值为 

对于每一组 ，可以兑换面值为 的旧硬币的个数为 ，不难推导出这是个关于 r 的二次函数，也就是其有极大值

枚举 r 并进行求解，最大值为：682425

ans = 0
for r in range(1012, 2023):
    # 目标面值
    tar = r * 2 + 1
    l = tar - 2023
    tmp = (l + r) * (r - l + 1) // 2
    # 无更优时退出
    if tmp < ans: break
    ans = tmp
    print(l, r, tmp)
print(ans)

1
2
3
4
5
6
7
8
9
10
11
12

C：松散子序列  91

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/452862