Python3求解指定范围内和为目标值的最大数优先最少元素组合

核心思路 #

要满足「元素个数最少」且「优先选尽可能大的数值」两个要求，我们可以用纯数学推导的方式避免低效的回溯或动态规划：

1. 元素个数最少等价于优先取最大的数，因为数值越大，凑到目标和需要的元素数量越少
2. 先找到最小的k值，使得1~n范围内最大的k个连续数的和大于等于目标和，此时k就是最少的元素个数
3. 计算最大k个连续数的和与目标和的差值，仅调整这k个数里最小的那个值抵消差值，其余大数全部保留，就能满足优先选大值的要求

实现步骤 #

• 读取输入的上限n和目标和s
• 用二分法查找最小的正整数k，满足公式 k*(2*n -k +1)//2 >= s，该公式是区间[n-k+1, n]的求和公式
• 计算差值d = k*(2*n -k +1)//2 - s
• 构造结果：如果d=0，结果就是[n-k+1, n-k+2, ..., n]；如果d>0，结果就是[n-k+1 -d] + [n-k+2, n-k+3, ..., n]

代码实现 #

def find_min_combination(n, target):
    # 二分查找最小的k
    left = 1
    right = n
    best_k = n
    while left <= right:
        mid = (left + right) // 2
        sum_mid = mid * (2 * n - mid + 1) // 2
        if sum_mid >= target:
            best_k = mid
            right = mid - 1
        else:
            left = mid + 1
    # 计算差值调整最小元素
    sum_k = best_k * (2 * n - best_k + 1) // 2
    d = sum_k - target
    res = []
    if d > 0:
        res.append(n - best_k + 1 - d)
    # 拼接剩余连续大数值
    for i in range(n - best_k + 2, n + 1):
        res.append(i)
    return res

# 读取输入并输出结果
n, s = map(int, input().split())
print(' '.join(map(str, find_min_combination(n, s))))

性能说明 #

• 二分查找的时间复杂度仅为O(log n)，构造结果的时间复杂度为O(k)，哪怕n达到1e6甚至更高的量级，也可以在毫秒级出结果，完全可以处理题目里的大数值输入场景
• 结果完全符合题目要求：元素个数是最小的可能值，且除了调整的最小元素外，其余全部是可选范围内最大的数值，满足优先选大值的规则

内容的提问来源于stack exchange，提问作者roula bahhadi