Python,还有2个点TLE,求助大家
查看原帖
Python,还有2个点TLE,求助大家
1024167
elxupanda楼主2024/7/5 06:22

还是有两个点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)
2024/7/5 06:22
加载中...