Topcoder Member SRM 503 Easy

沒參加，後來補做Easy。

題意﹕問兩個整數集合 $A, B$ ，能否各自劃分成 $k$ 個離散子集，使得 $A$ 和 $B$ 的第 $i$ 子集必然使得 $A$ 的數全部少於 $B$ 的數。 $k$ 最少是多少？保証 $A, B$ 的數沒重覆。首先想到可以這樣劃分…



但無論你怎樣做，都必然存在最多 $k = 2$ 。如下圖…



甚麼時候是 $k = 1$ ？就是當 $A$ 的最大值少於 $B$ 的最小值。
甚麼時候是 $k = -1$ ？就是當 $A$ 的最大值大於 $B$ 的最大值，或 $A$ 的最小值大於 $B$ 的最小值。