TLE (превышено ограничение по времени) Ошибка для Golang, но не для Python при использовании аналогичных логик c. Но почему?

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)
    }
}

Обновленное решение go с улучшенной временной сложностью O (n):

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 не использует буферизованный ввод-вывод . Вы можете исправить это, используя явный буфер и 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)
    }
}

Если даже этого недостаточно для какой-либо другой проблемы, есть еще один вопрос здесь с еще более быстрым решением .

Дополнительная оптимизация - это ненужное распределение массивов на каждой итерации. Поскольку вам дан максимально возможный размер, вы можете сделать

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

, а затем просто получить срез в каждой итерации

prices := container[0:houses]

и работать с этим. Это официальное сообщение в блоге очень хорошо объясняет внутренности.