题解：P7305 [COCI2018-2019#1] Cipele

这是一道练习二分的不错的题目。因为每组数据的答案的范围都可以被算出来，所以就可以对答案进行二分然后判断该答案是否合法即可，这样时间复杂度也会降到 $\log$ 级别，所以不会超时。

先来看看如何求答案的范围。为了方便程序的计算，以下保证 $n \le m$ (若出现 $n >m$ 的情况，则输入完毕后将 $n,m$ 以及 $L_i,R_i$ 进行交换)。对于所有左脚鞋 $L_i$ 都有一个右脚鞋 $R_i$ 满足 $L_i = R_i$ 的情况，则最小的答案为 $0$；将左右脚鞋子分别进行排序，由题对丑陋度的定义可知，最大的答案为 $\min (|L[1] - R[m]|,|R[1] - L[n]|)$。

得知范围后，接下来就是对答案的二分了。二分目的是要找到一个最小的合法答案，因此要写成 r = mid 与 l = mid + 1。

1
2
3
4
5
6

while (l < r)
{
    int mid = (l + r) >> 1;
    if (check (mid)) r = mid;
    else l = mid + 1;
}

那么如何判断解是否合法呢？设当前的待判断的答案为 $num$，用数量较少的鞋子去匹配数量较多的鞋子(由于前文规定了 $n < m$，也就是用左脚鞋去匹配右脚鞋)，利用贪心的思想，对于每一只已经从小到大排好的左脚鞋，要找到一只右脚鞋满足 $|L_i - R_j| \le num$ 后再去匹配下一只左脚鞋。若在左脚鞋满足在范围内全部成功与右脚鞋匹配的情况，则答案合法，否则不合法。

1
2
3
4
5
6
7
8
9
10
11

bool check (int num)//to check whether the answer is correct or not 
{
    int cnt = 1;
    for (int i = 1;i <= n;++i)
    {
        while (cnt <= m && abs (a[i] - b[cnt]) > num) ++cnt;//plus cnt until find a correct answer
        if (cnt > m) return 0; 
        ++cnt;//find it
    }
    return 1;
}

最后退出循环 while (l < r) 后得到的 $l$ 就是答案啦！