牛客真题编程——day5

编译环境&＃xff1a;c&＃43;&＃43;

1、马戏团

描述&＃xff1a;

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

算法思想&＃xff1a;

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

部分代码实现&＃xff1a;

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

2、二分查找

描述&＃xff1a;

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

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

算法思想&＃xff1a;

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

代码部分实现&＃xff1a;

3、年终奖

描述&＃xff1a;

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

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

算法思想&＃xff1a;

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

代码部分实现&＃xff1a;