python - Golang的TLE(超过时间限制)错误，但使用类似逻辑的Python则没有。但为什么？

Question

我为Google Kickstart编写了针对同一简单问题的两种解决方案。它们基本上是相同的解决方案。问题链接是this。我提交了两个解决方案，首先是go，然后是python。但是python解决方案可以正确执行，其中go解决方案具有TLE。我正在共享这两个代码。感谢您提供有关错误的反馈。

Go:

package main

import (
    "fmt"
    "sort"
)

func main() {
    var N int
    fmt.Scan(&N)
    for i := 1; i <= N; i++ {
        var house, budget int
        fmt.Scan(&house, &budget)
        prices := make([]int, house)
        for j := 0; j < house; j++ {
            fmt.Scan(&prices[j])
        }

        sort.Ints(prices)
        j := 0
        for ; j < house; j++ {
            if prices[j] > budget {
                break
            }
            budget -= prices[j]
        }
        fmt.Printf("Case #%d: %d\n", i , j)
    }
}

具有改进的时间复杂度O(n)的更新的go解决方案:

package main

import (
    "fmt"
)

func main() {
    var N int
    fmt.Scan(&N)
    for i := 1; i <= N; i++ {
        var house, budget int
        fmt.Scan(&house, &budget)
        prices := make([]int, 1000)
        for j, val := 0, 0; j < house; j++ {
            fmt.Scan(&val)
            prices[val-1]++
        }

        count := 0
        for j := 0; j < 1000; j++ {
            if prices[j] == 0 {
                continue
            }
            cost := prices[j] * (j + 1)
            if budget >= cost {
                budget -= cost
                count += prices[j]
            } else {
                c := budget / (j + 1)
                count += c
                break
            }
        }
        fmt.Printf("Case #%d: %d\n", i, count)
    }
}

Python:

N = int(input())

for i in range(1, N + 1):
    house, budget = map(int, input().split())
    prices = list(map(int, input().split()))
    prices.sort()
    j = 0
    for price in prices:
        if price > budget:
            break
        budget -= price
        j += 1
    print("Case #", i, ": ", j, sep='')

Answer 1

速度慢于输入读数。函数 fmt.Scan doesn't use buffered IO。您可以使用explicit buffer和 Fscan 修复此问题。

in := bufio.NewReader(os.Stdin)
fmt.Fscan(in, &N)

这样，即使算法缓慢的解决方案也能通过测试(是的，它好得多)

package main

import (
    "fmt"
    "sort"
    "bufio"
    "os"
)

func main() {
    var N int
    in := bufio.NewReader(os.Stdin)
    fmt.Fscan(in, &N)
    for i := 1; i <= N; i++ {
        var house, budget int
        fmt.Fscan(in, &house, &budget)
        prices := make([]int, house)
        for j := 0; j < house; j++ {
            fmt.Fscan(in, &prices[j])
        }

        sort.Ints(prices)
        j := 0
        for ; j < house; j++ {
            if prices[j] > budget {
                break
            }
            budget -= prices[j]
        }
        fmt.Printf("Case #%d: %d\n", i , j)
    }
}

如果即使对于某些其他问题来说这还不够快，那么还有另一个问题here，它的解决方案甚至更快。

另一个优化是在每次迭代中都注意到不必要的数组分配。由于已为您提供最大的尺寸，您可以

const maxAllocation = 10000
container := make([]int, maxAllocation)

然后在每次迭代中得到一个 slice

prices := container[0:houses]

并与之合作。这个official blog post很好地解释了内部原理。