还是有两个点TLE,请大家帮忙指正。我也看了一些AC同学的代码,但是我觉得有问题。简单从两边用指针的方式组合并非时最后组合解。
# 程序解法一:
w = int(input())
n = int(input())
lst = []
total = 0
for i in range(n): # 序列输入
x = int(input())
lst.append(x)
lst.sort(reverse=True) # 序列降序排序
def func(num):
for j in range(num):
for k in range(num-1, j, -1): # 从后向前遍历寻找最佳元素组合
if lst[j] + lst[k] == w and len(lst) != 1: # 找到相加等于阈值的组合, 注意要考虑最后只剩下一个元素的情况
lst.pop(j) # 找到后弹出相关的元素
lst.pop(k-1) # 注意:弹出后,列表的位置前移一个
return 1
elif lst[j] + lst[k] > w: # 因为是从小到大遍历寻找最佳组合,当出现前后的元素和大于阈值时,不再继续向前寻找
break
for k in range(j+1, num): # 当没有最佳元素组合后,从前向后遍历寻找次佳元素组合
if lst[j] + lst[k] <= w:
lst.pop(j)
lst.pop(k-1)
return 1
lst.pop(j) # 找不到组合的,单独弹出
return 1
for i in range(n):
if len(lst) != 0:
total += func(len(lst))
else:
break
print(total)