贪心与分治：五级综合

# 第一幕：找零机器人（贪心）
def change(amount):
    """用 10、5、2、1 元硬币找零，贪心：每次先拿最大面额"""
    coins = [10, 5, 2, 1]
    used = []
    for c in coins:
        while amount >= c:
            amount = amount - c
            used.append(c)
    return used

money = 37
plan = change(money)
print("找零", money, "元：", plan)
print("一共用了", len(plan), "枚硬币")

print("——————")

# 第二幕：归并排序（分治）
def merge_sort(nums):
    """分成两半各自排好，再合并成有序"""
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])    # 分而治之：左半边
    right = merge_sort(nums[mid:])   # 分而治之：右半边
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):   # 合并两个有序列表
        if left[i] <= right[j]:
            merged.append(left[i])
            i = i + 1
        else:
            merged.append(right[j])
            j = j + 1
    merged = merged + left[i:]
    merged = merged + right[j:]
    return merged

scores = [88, 45, 92, 61, 77, 54, 99, 38]
print("排序前：", scores)
print("排序后：", merge_sort(scores))

# 复杂度小估算：每层合并 n 个数，共约 log2(n) 层
import math
n = 1000000
print("百万数据归并：约", math.ceil(math.log2(n)), "层 × 每层百万次 ≈ 两千万次操作")