差分-golang
题目描述
输入一个长度为n的整数序列。
接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数n和m。
第二行包含n个整数,表示整数序列。
接下来m行,每行包含三个整数l,r,c,表示一个操作。
输出格式
共一行,包含n个整数,表示最终序列。
数据范围
1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000
输入样例:
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例:
3 4 5 3 4 2
数组使用 fmt.Scan(&q[i]) 超时
package main
import (
"bufio"
"fmt"
"strconv"
"strings"
)
const N = 100010
func main() {
var q [N]int
var b [N]int
n, m := 0, 0
fmt.Scanln(&n, &m)
// reader := bufio.NewReader(os.Stdin)
// line := readline(reader)
for i := 1; i <= n; i++ {
//q[i] = line[i-1]
fmt.Scan(&q[i])
b[i] = q[i] - q[i-1]
}
for m > 0 {
m--
// line = readline(reader)
// l, r, c := line[0], line[1], line[2]
l, r, c := 0, 0, 0
fmt.Scan(&l, &r, &c)
b[l] += c
b[r+1] -= c
}
for i := 1; i <= n; i++ {
q[i] = q[i-1] + b[i]
fmt.Printf("%d ", q[i])
}
}
func readline(reader *bufio.Reader) []int {
strline, _ := reader.ReadString('\n')
params := strings.Fields(strline)
line := make([]int, len(params))
for i, elem := range params {
line[i], _ = strconv.Atoi(elem)
}
return line
}
算法2
使用bufio.NewReader(), readString 从标准输入读出每行数据,然后赋值给数组, 搞定超时问题。
时间复杂度 O(n)
参考文献
golang 代码
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
const N = 100010
func main() {
var q [N]int
var b [N]int
n, m := 0, 0
fmt.Scanln(&n, &m)
reader := bufio.NewReader(os.Stdin)
line := readline(reader)
for i := 1; i <= n; i++ {
q[i] = line[i-1]
b[i] = q[i] - q[i-1]
}
for m > 0 {
m--
line = readline(reader)
l, r, c := line[0], line[1], line[2]
b[l] += c
b[r+1] -= c
}
for i := 1; i <= n; i++ {
q[i] = q[i-1] + b[i]
fmt.Printf("%d ", q[i])
}
}
func readline(reader *bufio.Reader) []int {
strline, _ := reader.ReadString('\n')
params := strings.Fields(strline)
line := make([]int, len(params))
for i, elem := range params {
line[i], _ = strconv.Atoi(elem)
}
return line
}
优化 方案三
使用bufio.NewScanner来做,结果默认的scanner 缓冲区 太小, 输入的行超大, 缓冲区溢出了。 手动申请大缓冲区来读输入。完美解决。 此方案参考了 custer-go 同学的方案 。 https://www.acwing.com/solution/content/21728/
code
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
n, m := 0, 0
fmt.Scanln(&n, &m)
q := make([]int, n+10)
b := make([]int, n+10)
scanner := bufio.NewScanner(os.Stdin)
buf := make([]byte, 100000*16) //输入范围最大十万个数, 每个整数占8个字节。 申请 10w * 16 防止溢出。
scanner.Buffer(buf, len(buf))
scanner.Scan()
line := strings.Split(scanner.Text(), " ")
for i := 1; i <= n; i++ {
q[i], _ = strconv.Atoi(line[i-1])
b[i] = q[i] - q[i-1]
}
var questionParam [3]int
for m > 0 {
m--
scanner.Scan()
temp := strings.Split(scanner.Text(), " ")
for k, v := range temp {
questionParam[k], _ = strconv.Atoi(v)
}
l, r, c := questionParam[0], questionParam[1], questionParam[2]
b[l] += c
b[r+1] -= c
}
for i := 1; i <= n; i++ {
q[i] = q[i-1] + b[i]
fmt.Printf("%d ", q[i])
}
}