记录-华为机试(五) | 不爱吃香菜的萌新

URL

type

status

date

slug

summary

📝 算法题

第一题:合唱队

描述:

音乐课上，老师将n位同学排成一排。老师希望在不改变同学相对位置的前提下，从队伍中选出最少数量的同学，使得剩下的同学排成合唱队形。记合唱队形中一共有k位同学，记编号为 1,2,…,k，第i个人的身高为hi。要求：存在一位同学编号为i(1<i<k)，使得 h1,h2,…,hi−1严格递增，且 hi+1,hi+2,…,hk严格递减；更具体地，合唱队形呈 h1<h2<⋯<hi−1<hi、hi>hi+1>⋯>hk。你能帮助老师计算，最少需要出列多少位同学，才能使得剩下的同学排成合唱队形？

输入描述:

第一行输入一个整数n(1≦n≦3000)代表同学数量。第二行输入n个整数 h1,h2,…,hn(0≦hi≦10^5)代表每一位同学的身高。

输出描述:

输出一个整数，代表最少需要出列的同学数量。

解决方法:

思路:动态规划。动态规划是将所有情况都记录在数组集合中，然后寻找目标值。在该算法中，遍历所有情况，有两种方法：第一种是二分法，第二种是穷举。

第一种:二分法

这里的二分法指的是代码中查找index所用的方法是二分法，并不是整个函数都是二分法。首先，建立两个数组，分别是dp和leng。dp用来记录当前元素和其之前的元素可组成最长的升序序列（包含当前序列）。leng用来记录当前元素在其之前元素的组成的最长升序序列的位置（包含当前元素）。便于理解，博主做了一张图辅助理解，如下：