P7305 [COCI2018-2019#1] Cipele 题解

· · 个人记录

题目传送门

很显然这题答案有单调性，于是考虑二分。

二分答案（求最小值）模板：

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

其中，check 函数就是判断条件。怎么判断呢？显然随意匹配肯定不行，于是考虑排序。这样，如果第 a_i 个鞋子与第 b_j 个鞋子的丑陋值如果不满足条件，那么第 i + 1 个鞋子显然也不行了。想到这里，函数就已经完成一半了。但是， n 不一定小于 m ，如果大于 m ，就要把比较的对象互换，因为 n 只鞋子是肯定不能组成 m 双的。 函数代码如下：

bool check(int mi)
{
    int cn = 0,un = 0;
    if(n < m)
    {
        for(int i = 1;i <= n;i ++)
            for(int j = cn + 1;j <= m;j ++)
                if(abs(a[i] - b[j]) <= mi)
                {
                    un ++;
                    cn = j;
                    break;
                }
    }
    else
    {
        for(int i = 1;i <= m;i ++)
            for(int j = cn + 1;j <= n;j ++)
                if(abs(b[i] - a[j]) <= mi)
                {
                    un ++;
                    cn = j;
                    break;
                }
    }
    return un >= min(n,m);
}

AC code:

#include <iostream>
#include <algorithm>
using namespace std;
long long n,m,a[1000005],b[1000005],l,r = 1e10;
bool check(int mi)
{
    int cn = 0,un = 0;
    if(n < m)
    {
        for(int i = 1;i <= n;i ++)
            for(int j = cn + 1;j <= m;j ++)
                if(abs(a[i] - b[j]) <= mi)
                {
                    un ++;
                    cn = j;
                    break;
                }
    }
    else
    {
        for(int i = 1;i <= m;i ++)
            for(int j = cn + 1;j <= n;j ++)
                if(abs(b[i] - a[j]) <= mi)
                {
                    un ++;
                    cn = j;
                    break;
                }
    }
    return un >= min(n,m);
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)cin >> a[i];
    for(int i = 1;i <= m;i ++)cin >> b[i];
    sort(a + 1,a + n + 1);
    sort(b + 1,b + m + 1);
    while(l < r)
    {
        int mid = (l + r) / 2;
        if(check(mid))r = mid;
        else l = mid + 1;
    }
    cout << r;
}