forked from EndlessCheng/codeforces-go
-
Notifications
You must be signed in to change notification settings - Fork 0
/
118C.go
53 lines (49 loc) · 1003 Bytes
/
118C.go
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
package main
import (
"bufio"
. "fmt"
"io"
"math"
)
// https://space.bilibili.com/206214
func CF118C(in io.Reader, out io.Writer) {
var n, k int
var s, ans string
Fscan(bufio.NewReader(in), &n, &k, &s)
pos := ['9' + 1][]int{}
for i, b := range s {
pos[b] = append(pos[b], i)
}
minCost := math.MaxInt
for c := byte('0'); c <= '9'; c++ {
t := []byte(s)
cost := 0
left := k - len(pos[c])
for d := byte(1); d <= 9; d++ {
if c+d <= '9' { // 先改比 c 大的
p := pos[c+d]
for i := 0; i < len(p) && left > 0; i++ { // 正序
t[p[i]] = c
left--
cost += int(d)
}
}
if c-d >= '0' { // 再改比 c 小的
p := pos[c-d]
for i := len(p) - 1; i >= 0 && left > 0; i-- { // 逆序
t[p[i]] = c
left--
cost += int(d)
}
}
}
res := string(t)
if cost < minCost || cost == minCost && res < ans {
minCost = cost
ans = res
}
}
Fprintln(out, minCost)
Fprint(out, ans)
}
//func main() { CF118C(os.Stdin, os.Stdout) }