0921电信秋招笔试复盘
#牛客AI配图神器#1.
题目大意:从两组带时间属性的任务中各选一个,自由安排顺序,求完成两个任务的最早结束时间。
思路:暴力枚举O(nm)会超时。对一类课程按开始时间排序并预处理前缀/后缀最优值,然后遍历另一类课程,通过二分查找快速匹配最优的后续课程。双向计算取最终结果。
2.
题目大意:给定一个序列,可选择在某些位置安放标记。未安放标记的位置,若其相邻位置有标记,则该位置的值计入总和。求最大总和。
思路:先将网格按列求和降维成一维序列问题。然后DP
3.
题目大意:在网格中寻找带成本的最短路,其中包含k次特殊的零成本“跳跃”机会,跳跃受限于格子成本。
思路:将状态定义为(坐标,已用跳跃次数),跑一下dijkstra
#发面经攒人品#
题目大意:从两组带时间属性的任务中各选一个,自由安排顺序,求完成两个任务的最早结束时间。
思路:暴力枚举O(nm)会超时。对一类课程按开始时间排序并预处理前缀/后缀最优值,然后遍历另一类课程,通过二分查找快速匹配最优的后续课程。双向计算取最终结果。
2.
题目大意:给定一个序列,可选择在某些位置安放标记。未安放标记的位置,若其相邻位置有标记,则该位置的值计入总和。求最大总和。
思路:先将网格按列求和降维成一维序列问题。然后DP
3.
题目大意:在网格中寻找带成本的最短路,其中包含k次特殊的零成本“跳跃”机会,跳跃受限于格子成本。
思路:将状态定义为(坐标,已用跳跃次数),跑一下dijkstra
#发面经攒人品#
全部评论
相关推荐
09-27 10:30
门头沟学院 研发工程师 IIIIIc:可以这样想 从左到右进行匹配 因为题目保证有合法解,所以左括号数=右括号数。从左到右线性遍历,第一个匹配不上的一定是右括号多了一个,这个时候只需要把这个右括号和从右往左找第一个左括号进行交换,就是最优解,线性遍历统计即可。

点赞 评论 收藏
分享

点赞 评论 收藏
分享

点赞 评论 收藏
分享