拼多多9.22笔试求解

go写的
第二题思路是用一个map存出现过的整数数量，然后只要判断减去的两个数等于2*avg就可以，这个思路只过了36%

第四题dp，有券的时候可以用或不用取最小，有效期每轮-1，代码如下：
package main

import (
"fmt"
"strconv"
)

func main() {
T := 0
fmt.Scan(&T)
for t := 0; t < T; t++ {
n := 0
fmt.Scan(&n)
nums := make([]int, n)
for j := 0; j < n; j++ {
fmt.Scan(&nums[j])
}
m := make(map[triple]int)
var dfs func(int, int, string) int
dfs = func(i, credit int, valid string) int {
if i == n-1 {
if valid != "" {
return 0
} else {
return nums[i]
}
}
if val, ok := m[triple{i, credit, valid}]; ok {
return val
}
res := 0
if valid == "" {
credit += nums[i]
if credit >= 100 {
credit -= 100
valid = "3"
}
res += dfs(i+1, credit, valid) + nums[i]
} else if valid[0] == '1' {
res += dfs(i+1, credit, minus1(valid[1:]))
} else {
if credit+nums[i] >= 100 {
a := credit + nums[i] - 100
res += min(dfs(i+1, credit, minus1(valid[1:])), nums[i]+dfs(i+1, a, minus1(valid)+"3"))
} else {
res += min(dfs(i+1, credit, minus1(valid[1:])), nums[i]+dfs(i+1, credit+nums[i], minus1(valid)))
}
}
m[triple{i, credit, valid}] = res
return res
}
fmt.Println(dfs(0, 0, ""))
}
fmt.Println(minus1("123"))
}

func minus1(s string) string {
res := ""
for _, v := range s {
v1, _ := strconv.Atoi(string(v))
v1--
if v1 > 0 {
res += strconv.Itoa(v1)
}
}
return res
}

type triple struct {
i      int
credit int
valid  string
}

func min(a, b int) int {
if a < b {
return a
}
return b
}