Kick Start Round A 2021 - Rabbit House

发表于 | 分类于

原题地址: 传送门

分析

对于英文弱鸡的笔者，这道题着实看了很久才看懂题意，同样在一个二维平面内存在着R * C的格子，且每个格子都会有0≤ Gi,j ≤2*10^6各盒子，例如：

1
2
3
0 0 0
0 2 0
0 0 0

上述表示R为3，C为3的格子，中间格子的盒子数量为2，其余格子盒子数量为0。

描述到此为止，最终问题是求输入的R*C的格子中，如果要保证每个格子与相邻格子的盒子数量差在1以内，需要在当前规格的基础上，至少增加多少个盒子？

因为最终要保证整个平面内，所有的格子高度差绝对值 <= 1，所以应该从最高的格子开始，让其相邻格子条件，之后除去当前格子，再取剩下格子中最高的格子循环处理，直到当前最高的格子高度为1时结束循环，将新增的盒子数作为答案输出。

分析后的问题转化为将格子从高到低排列，并优先取出最高的格子做处理，并且格子的高度排列是会随着处理过程发生变化，所以使用优先队列处理之！

Solve

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var res = make([]int, 0)

var in = bufio.NewReader(os.Stdin)

func solve(){
	inputs := readInts(in)
	r := inputs[0]
	c := inputs[1]
	grid := make([][]int, r)
	for i := 0; i < r; i ++ {
		grid[i] = readInts(in)
	}

	nodes := &nodes{}
	for i := 0; i < r; i ++ {
		for j := 0; j < c; j++ {
			heap.Push(nodes, node{
				val: grid[i][j],
				x: j,
				y: i,
			})
		}
	}
	m := 0
	for ;;{
		if nodes.Len() == 0{
			break
		}
		n := heap.Pop(nodes).(node)
		if n.val != grid[n.y][n.x] {
			continue
		}
		if n.x > 0 {
			if n.val - grid[n.y][n.x - 1] > 1{
				m += n.val - grid[n.y][n.x - 1] - 1
				grid[n.y][n.x - 1] = n.val - 1
				heap.Push(nodes, node{
					val: grid[n.y][n.x - 1],
					x: n.x - 1,
					y: n.y,
				})
			}
		}
		if n.x < c -1 {
			if n.val - grid[n.y][n.x + 1] > 1{
				m += n.val - grid[n.y][n.x + 1] - 1
				grid[n.y][n.x + 1] = n.val - 1
				heap.Push(nodes, node{
					val: grid[n.y][n.x + 1],
					x: n.x + 1,
					y: n.y,
				})
			}
		}
		if n.y > 0 {
			if n.val - grid[n.y - 1][n.x] > 1{
				m += n.val - grid[n.y - 1][n.x] - 1
				grid[n.y - 1][n.x] = n.val - 1
				heap.Push(nodes, node{
					val: grid[n.y - 1][n.x],
					x: n.x,
					y: n.y - 1,
				})
			}
		}
		if n.y < r - 1 {
			if n.val - grid[n.y + 1][n.x] > 1{
				m += n.val - grid[n.y + 1][n.x] - 1
				grid[n.y + 1][n.x] = n.val - 1
				heap.Push(nodes, node{
					val: grid[n.y + 1][n.x],
					x: n.x,
					y: n.y + 1,
				})
			}
		}
	}
	res = append(res, m)
}

func main()  {
	t := readInts(in)[0]
	for i := 0; i < t; i ++ {
		solve()
	}
	for i, v := range res {
		fmt.Printf("Case #%d: %d\n", i + 1, v)
	}
}

func readline(in *bufio.Reader) string{
	line, _ := in.ReadString('\n')
	return line[0:len(line) - 1]
}

func readInts(in *bufio.Reader) []int{
	line := readline(in)
	arr := strings.Split(line, " ")
	res := make([]int, 0)
	for _, str := range arr {
		v, _ := strconv.ParseInt(str, 10, 64)
		res = append(res, int(v))
	}
	return res
}

type node struct {
	val int
	x int
	y int
}

type nodes []node

func (t *nodes) Len() int {
	return len(*t) //
}

func (t *nodes) Less(i, j int) bool {
	return (*t)[i].val >= (*t)[j].val
}

func (t *nodes) Swap(i, j int) {
	(*t)[i], (*t)[j] = (*t)[j], (*t)[i]
}

func (t *nodes) Push(x interface{}) {
	*t = append(*t, x.(node))
}

func (t *nodes) Pop() interface{} {
	n := len(*t)
	if n > 0 {
		x := (*t)[n-1]
		*t = (*t)[:n-1]
		return x
	}
	return -1
}

func (t *nodes) Peek() interface{} {
	n := len(*t)
	if n > 0 {
		return (*t)[0]
	}
	return -1
}