题解：P10356 [PA2024] Splatanie ciągów

C1942huangjiaxu · 2024-04-29 20:36:54 · 题解

先考虑给定 2 个单调递增的数组 A,B，怎么求 f(A,B)。

不妨设 A 长度为 |A|=n，B 长度为 |B|=m，n\ge m。

那么我们考虑往 A 中插入 B，假如插入 x 在 a_i,a_{i+1} 之间，可以发现 a_i\lt x 和 x\lt a_{i+1} 至少满足 1 个，假如 2 个都满足，那么我们可以交换 x 和 a_i，这样一定不劣。

所以我们可以看做用 m 个数，把 A 分成了 m+1 段，但因为插入每个数都会满足一个递增条件，那么就是把 n+m 个数分成了 m+1 段，也就是说我们构造出的答案为 \lceil \frac {n+m}{m+1}\rceil，同时可以发现这就是答案的下界。

因此，有 f(A,B)=\lceil \frac {n+m}{m+1}\rceil。

也就是说，对于长度为 n 的单调序列，要使答案不超过 x，那么 m 要满足 \lceil \frac {n+m}{m+1}\rceil \le x，解得 m\ge \lceil \frac {n-x}{x-1}\rceil。

现在令 a_i 表示 A 中的极长单调区间的长度，例如 A=[1,2,3,4,8,7,6,5]，有极长单调区间 [1,2,3,4,8] 和 [8,7,6,5]，所以 a=[5,4]。