A 配对


题意:给定两个数列,求出这两个数列第K大的和的最大值


解答:从大到小排列,因为要使得前K大尽可能的大

那么范围一定是在两个数组前K大的数里面进行选择

相当于这K对数字的最小值要最大

那么只需要两个里面按照大小关系两两配对即可

即最大的与最小的配对,第二大的和第二小的配对

最后输出最小值即可



C 汉诺塔


题意:给定一堆木板,要往柱子上面放,放在下面的木板一定要比放在上面的木板两条边严格大于,并且不可以旋转这个木板,问最少需要多少柱子


解答:用res来存下每一个柱子的情况,先sort一下所有的木板,每加入一个新的木板,就二分查找到res里面最小的木板且刚好满足题意的情况,并更新一下res即可

需要特别注意下还要输出一下每一个木板在哪里,在排序之前记录一下id



D 重排列


题意:给定两个序列,你可以随意重新组合这两个序列,问有多少种序列可以满足对任意\( i \leq j\)有\(a_i \leq a_j\),其中相同的元素视作不同


解答:对A序列从大到小遍历,因为大的才会影响后面的选择,然后每看到一个数字就看B序列里面有多少个是大于A序列里面的元素的,然后对res乘上元素个数减去前面的元素



F 十字阵列


题意:扔炸弹,对x行和y列造成z点伤害,假设最后第i行第j列伤害是\( w_{ij} \)问最后\( \Sigma w_{ij}(i+j) \)的值是多少


解答:和翻转棋升级版很像,大概就是记录一下每一行出现多少次,每一列有多少伤害,注意这里第i行第j列的伤害只计算一次,需要减掉



G 括号序列


题意:给一个括号序列,问最少删除多少个括号,可以使得括号匹配


解答:用类似于括号匹配的方法来进行操作,在匹配的时候判断一下能不能匹配(判断一下栈里面有没有东西),不能匹配就删掉这个就可以了,注意最后要加上不能匹配的左括号的数量(即栈的size)



I 导航系统


题意:给定一棵树所对应的邻接矩阵,问这个邻接矩阵能否自洽,如果可以还需要输出最短的i-1条边


解答:最小生成树跑出来结果,然后Floyd运行出最小生成树对应的邻接矩阵观察是否相同即可



J 签到题


题意:给定一个三角形的三条边,问从三个顶点做出的三个外切圆半径


解答:二分一个外切圆半径,然后判断三角形里面能否成立即可,注意二分大小关系


 

分类: 牛客

0 条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注