求助,并非左右脑的贪心DFS,为什么全WA??
查看原帖
求助,并非左右脑的贪心DFS,为什么全WA??
928373
Dec_04_CWJ楼主2025/1/17 23:29
def dfs(arr):
    n = len(arr)
    if n == 0:
        return 0
    if n == 1:
        return arr[0]
    if n == 2:
        return max(arr[0], arr[1])
    arr.sort()
    ans = 0
    # 同时执行arr[0]和arr[len-1]
    ans += arr[n - 1]
    if arr[n - 1] - arr[0] < arr[n - 2]:
        arr[n - 2] -= arr[n - 1] - arr[0]
        del arr[n - 1]
        del arr[0]
        ans += dfs(arr)
    elif arr[n - 1] - arr[0] == arr[n - 2]:
        del arr[n - 1]
        del arr[n - 2]
        del arr[0]
        ans += dfs(arr)
    elif arr[n - 1] - arr[0] > arr[n - 2]:
        temp = arr[n - 1] - arr[0] - arr[n - 2]
        if n >= 4:
            arr[n - 3] -= temp
        del arr[n - 1]
        del arr[n - 2]
        del arr[0]
        ans += dfs(arr)
    return ans


s1, s2, s3, s4 = list(map(int, input().split()))
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))
arr3 = list(map(int, input().split()))
arr4 = list(map(int, input().split()))
time1 = dfs(arr1)
time2 = dfs(arr2)
time3 = dfs(arr3)
time4 = dfs(arr4)
time = time1 + time2 + time3 + time4
print(time)

有点想不明白,为什么我这个不行,我的用例是能通过,但是就是爆0了,我这个我也不知道是贪心还是递归,反正就是出不来,求大佬帮助!!!

2025/1/17 23:29
加载中...