package main import ( "fmt" "io" ) // 重点函数 // 用动态规划来求解递增数列 func returnRankSlice(numSlice []int, rankSlice []int) []int { // 初始化递增数列 // 值都设置为1(因为至少包括自己本身) for i := 0; i < len(rankSlice); i++ { rankSlice[i] = 1 } for i := 0; i < len(numSlice); i++ { var max int for j := 0; j < i; j++ { if numSlice[j] < numSlice[i] { if rankSlice[j] >= max { max = rankSlice[j] } } } rankSlice[i] = max + 1 } return rankSlice } func main() { for { // 输入人员人数 var num int _, err := fmt.Scan(&num) if err == io.EOF { break } // 用切片来存储该组人员的身高 numSlice := make([]int, num) for i := 0; i < num; i++ { // 循环输入身高 var height int fmt.Scan(&height, " ") numSlice[i] = height } // 求出递增序列 tempNumSlice1 := make([]int, num) incrNumSlice := returnRankSlice(numSlice, tempNumSlice1) // 求出反转的 numSlice var reNumSlice []int for i := len(numSlice) - 1; i >= 0; i-- { reNumSlice = append(reNumSlice, numSlice[i]) } // 求出递减序列 tempNumSlice2 := make([]int, num) deNumSlice := returnRankSlice(reNumSlice, tempNumSlice2) // 求出反转的递减序列 var reverseDeNumSlice []int for i := len(deNumSlice) - 1; i >= 0; i-- { reverseDeNumSlice = append(reverseDeNumSlice, deNumSlice[i]) } // 得到剩下的K位同学最大值 var maxNum int for i := 0; i < len(reverseDeNumSlice); i++ { tempNum := reverseDeNumSlice[i] + incrNumSlice[i] - 1 if tempNum > maxNum { maxNum = tempNum } } // 总人数 - 剩下的K位同学的最大值 = 最少需要几位同学出列 fmt.Println(num - maxNum) } }
该题的难点在于用动态规划来求解递增数列
按顺序遍历每位同学的身高,后面的递增数列的值需要通过动态规划,由前面的值得到。
因此,如果有同样想用 Go 语言求解这道题目的同学,可以重点把我写的函数:
returnRankSlice(numSlice []int, rankSlice []int) []int
搞明白,那么,接下来问题的处理逻辑就很简单了