牛客真题编程——day5

编译环境:c++

1、马戏团

描述:

搜狐员工小王最近利用假期在外地旅游,在某个小镇碰到一个马戏团表演,精彩的表演结束后发现团长正和大伙在帐篷前激烈讨论,小王打听了下了解到, 马戏团正打算出一个新节目“最高罗汉塔”,即马戏团员叠罗汉表演。考虑到安全因素,要求叠罗汉过程中,站在某个人肩上的人应该既比自己矮又比自己瘦,或相等。 团长想要本次节目中的罗汉塔叠的最高,由于人数众多,正在头疼如何安排人员的问题。小王觉得这个问题很简单,于是统计了参与最高罗汉塔表演的所有团员的身高体重,并且很快找到叠最高罗汉塔的人员序列。 现在你手上也拿到了这样一份身高体重表,请找出可以叠出的最高罗汉塔的高度,这份表中马戏团员依次编号为1到N。

算法思想:

题目要求,录入N个人员信息,根据他们的身高体重,得到一个满足下层人员身高、体重>=上层员工的最大子序列长度。首先我们按照体重,对所有的员工进行升序排序,当体重相同时,按照身高降序排序。再声明一个记录高度的数组,长度为N,对应n个员工在罗汉塔的位置。对排序后的员工进行遍历,当a[i].height >= a[j].height时,更新对应员工的所在高度。每次遍历完更新最大的高度数。遍历完成,输出的结果即为罗汉塔的最大高度。

部分代码实现:

牛客真题编程——day5_第1张图片

这里用到了algorithm中排序的bool类型的优先级cmp函数,定义结构体存储员工信息。

2、二分查找

描述:

对于一个有序数组,我们通常采用二分查找的方式来定位某一元素,请编写二分查找的算法,在数组中查找指定元素。

给定一个整数数组A及它的大小n,同时给定要查找的元素val,请返回它在数组中的位置(从0开始),若不存在该元素,返回-1。若该元素出现多次,请返回第一次出现的位置。

算法思想:

    根据二分法思想,有有序数组为前提,首先将查找元素和数组中间元素进行比较,相等则输出;<中间元素时,取中值左边的一半长度的数组;>中间元素时,取中值右边的一半长度数组。输出时还需要判断它是否为第一次出现,即循环查找当前索引前是否还有相同大小的值,当第一次与查找元素不相等,打印输出索引值+1。

代码部分实现:

牛客真题编程——day5_第2张图片

3、年终奖

描述:

小东所在公司要发年终奖,而小东恰好获得了最高福利,他要在公司年会上参与一个抽奖游戏,游戏在一个6*6的棋盘上进行,上面放着36个价值不等的礼物,每个小的棋盘上面放置着一个礼物,他需要从左上角开始游戏,每次只能向下或者向右移动一步,到达右下角停止,一路上的格子里的礼物小东都能拿到,请设计一个算法使小东拿到价值最高的礼物。

给定一个6*6的矩阵board,其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值,保证每个礼物价值大于100小于1000。

算法思想:

    动态规划思想,因为只能向右和向下走,直到终点位置。所以就有当前位置的价值最优=当前位置的价值+max(左邻价值最优,上邻价值最优)。从起始位置出发,循环遍历整个二维数组,得到的a[N][N]即为可获得的最大价值。

代码部分实现:

 

 

你可能感兴趣的