A.选择数字
思路分析:
当时没有想到取特殊值,而是暴力对a, b数组进行枚举,二分判断a[i] + b[j]是否在a, b数组内。
@@
可以直接取a, b数组的最大值即可。
注意可以用max存线性扫描时的最大值即可,不用排序。
B.最大中位数
思路分析:
当时想到的是直接对原数组的中位数及以上部分增大即可,考虑[mid, max]区间加上k后的最小值,这样[min, mid)区间不用浪费k,也占据了低一半的数。
问题在于该思路实现起来可能比较复杂(也可能是自己不熟练)
@@
较简便的思路是二分答案,对结果的中位数进行二分,判断是否满足k。这样做的前提是目标满足单调性,即若mid符合条件,则mid1小于mid也符合条件,可以二分区间。
C.数字移动
思路分析:
当时没有做出来(/😅)
@@
题目是一个求环的模型。求移动的次数等价于求每个环的长度。
可以用tarjan算法求强连通分量,输出每个连通分量块的大小。
也可以用dfs或两个迭代数组求环。
由于这道题中为简单环,等价于连通块(一个环是一个连通块,一个连通块也是一个环),可以用并查集求连通块的大小。