如何缩短执行时间

Question

I was writing this code for "competitive Programming". It consisted of only 1 loop but gave "Time Limit Exceed" if n = 100000. Can Go be considered for competitive Programming?

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 -- Average Superhero Gang Power"

Answer 1

Go execution time can be improved to milliseconds for n = 100000, under the 1 second time limit.

---

For example, a complete solution to the problem,

// 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
", avg)
}

Output:

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

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

---

A benchmark for a cast of avengers with random powers, where n := 100000, k := 100, and 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
$