小米笔试3月23日“移山”答案

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	var n, m int
	input := bufio.NewScanner(os.Stdin)
	if input.Scan() {
		line := input.Text()
		arr := strings.Split(line, " ")
		n, _ = strconv.Atoi(arr[0])
		m, _ = strconv.Atoi(arr[1])
	}
	a := make([]int64, n)
	if input.Scan() {
		line := input.Text()
		arr := strings.Split(line, " ")
		for i := 0; i < len(arr); i++ {
			a[i], _ = strconv.ParseInt(arr[i], 10, 64)
		}
	}
	var l, r, h int
	var d []int
	x := 0
	for i := 0; i < m; i++ {
		x++
		// 差分数组，+2防止越界，也可以使用if
		d = make([]int, n+1)
		if input.Scan() {
			line := input.Text()
			arr := strings.Split(line, " ")
			l, _ = strconv.Atoi(arr[0])
			r, _ = strconv.Atoi(arr[1])
			h, _ = strconv.Atoi(arr[2])
		}
		d[l-1] = d[l-1] + h
		d[r] = d[r] - h
		for j := 1; j <= n; j++ {
			d[j] += d[j-1]
		}
		for j := 0; j < n; j++ {
			a[j] -= int64(d[j])
			if a[j] <= 0 {
				fmt.Println(x)
				return
			}
		}
		fmt.Println(a)
	}

}

//6 5
//8 9 10 25 36 63
//1 2 10

//5 4
//6 5 3 4 6
//1 3 2
//4 4 2
//3 5 1
//1 5 6

使用前缀和+差分数组做的，一定记得使用uint64，不然用例通过不了。