拼多多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
}
全部评论

相关推荐

投递Momenta等公司10个岗位 > 秋招joker 简历被挂麻了,求建议
点赞 评论 收藏
分享
死在JAVA的王小美:哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈,我也是,让我免了一轮,但是硬气拒绝了
点赞 评论 收藏
分享
shtdbb_:还不错,没有让你做了笔试再挂你
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-07 17:00
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务