Как улучшить время выполнения в го

Question

Я писал этот код для «соревновательного программирования».Он состоял только из 1 цикла, но давал «Превышение лимита времени», если n = 100000. Может ли Go быть рассмотрен для конкурентного программирования?

fmt.Scanln(&n, &k, &m)
for i := 0; i < n; i++ {
    fmt.Scanf("%d", &z)
    if m >= 0 {
        if z > x {
            x = z
            m--
        }
        if i == n-1 {
            m++
        }
    } else {
        if cnt == 0 {
            x = 0
        }
        x += z
        cnt++
    }
}
if m == 0 {
    f = float64(x / (n - m))
}
if k < m {
    x += k
} else {
    x += m
}
f = float64(x)
fmt.Println(f)

---

" codeforces.com / problemset / problem /1111 / B - Средняя сила банды супергероев "

Answer 1

Время выполнения Go может быть увеличено до миллисекунд для n = 100000 при ограничении времени в 1 секунду.

---

Например, полное решение проблемы,

// Problem - 1111B - Codeforces
// B. Average Superhero Gang Power
// http://codeforces.com/problemset/problem/1111/B

package main

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

func readInt(s *bufio.Scanner) (int, error) {
    if s.Scan() {
        i, err := strconv.Atoi(s.Text())
        if err != nil {
            return 0, err
        }
        return i, nil
    }
    err := s.Err()
    if err == nil {
        err = io.EOF
    }
    return 0, err
}

func main() {
    s := bufio.NewScanner(os.Stdin)
    s.Split(bufio.ScanWords)

    var n, k, m int
    var err error
    n, err = readInt(s)
    if err != nil {
        panic(err)
    }
    if n < 1 || n > 10e5 {
        panic("invalid n")
    }
    k, err = readInt(s)
    if err != nil {
        panic(err)
    }
    if k < 1 || k > 10e5 {
        panic("invalid k")
    }
    m, err = readInt(s)
    if err != nil {
        panic(err)
    }
    if m < 1 || m > 10e7 {
        panic("invalid m")
    }

    a := make([]int, n)
    sum := int64(0)
    for i := 0; i < n; i++ {
        ai, err := readInt(s)
        if err != nil {
            panic(err)
        }
        if ai < 1 || ai > 10e6 {
            panic("invalid a")
        }
        a[i] = ai
        sum += int64(ai)
    }
    sort.Slice(a, func(i, j int) bool {
        return a[i] > a[j]
    })

    i, ik := 0, k
    for ; m > 0; m-- {
        j := len(a) - 1
        if j >= 1 && (int64(n-1)*(1+sum) < int64(n)*(sum-int64(a[j]))) {
            // delete
            sum -= int64(a[j])
            a = a[:j]
        } else {
            // increment
            sum++
            a[i]++
            ik--
            if ik <= 0 {
                ik = k
                i++
                if i >= len(a) {
                    break
                }
            }
        }
    }

    // fmt.Println(sum, len(a))
    avg := float64(sum) / float64(len(a))

    fmt.Printf("%.20f\n", avg)
}

Вывод:

$ go run heroes.go
2 4 6
4 7
11.00000000000000000000
$ 

$ go run heroes.go
4 2 6
1 3 2 3
5.00000000000000000000
$ 

---

Точка отсчета для мстителей со случайными способностями, где n := 100000, k := 100 и m := 100000:

$ ls -s -h heroes.test
676K heroes.test
$ go build heroes.go
$ time ./heroes < heroes.test
708329.74652807507663965225
real    0m0.067s
user    0m0.038s
sys     0m0.004s
$