algorithms

LC4: Median of Two Sorted Arrays

Problem Leetcode 4: Median of Two Sorted Arrays There are two sorted arrays nums1 and nums2 of size $m$ and $n$ respectively. Find the median of the two sorted arrays. You may assume nums1 and nums2 cannot be both empty. Solution Linear Time 首先, 拿到这道求两个有序数组中位数的题, 我们先有一个baseline, 无论是每个数组用两个指针移动去比大小, 还是建一个新数组去把两个有序数组比完大小存进去然后直接 len(array)/2 一步解千愁, 至少我们有一个worst case是 $O(m+n)$ 的解决方案. Logarithmic Time I 当然, 我们不能这么没有出息对吧! 接下来, 我们就要考虑能否在一个$O(log(n))$的时间内解决这个问题. 既然是要一个对数的时间复杂度, 那我们就有了基本思想, 至少是固定倍数的去简化这个问题: 分别获取两个数组的中位数进行比较. 分别截取中位数大的数组的左半部分和中位数小的数组的左半部分.

CF Edu Round 37

A Problem 有一个水池如下图, 有从$1$ 到 $n$ 共 $n$ 个槽. 其中有 $k$ 个被注满水. 如果打开阀门的话, 水会从该槽中流到相邻的两个槽. 一秒过后, 隔壁的两个槽都被注水. 我们假设在完整的一秒过后才会被注水, 而不考虑不到一秒的情况. 我们的Max想要同时打开所有的阀门, 现在他想知道全部水槽都被注水的最短时间. I/O 第一行输入一个整数 $t$, 需要解决的情况个数($1 \leq t \leq 200$). 接下来有 $t$ 个情况, 每个情况有两个整数, $n$ 和 $k$ ($1 \leq n \leq 200, 1 \leq k \leq n$), 水槽的数量和注水槽的数量. 接下来是 $k$ 个整数 $x_i$ ($1 \leq x_i \leq n$) 表示第 $i$ 个注水槽的位置. 保证对任意 $2 \leq i \leq k$, 有 $x_{i-1} < x_i$. 每个情况输出一个整数, 即最少需要的时间.