P7305 题解

· · 题解

题面

Part1

不难发现，此题的最小丑陋值（即答案）具有单调性，因此我们可以使用二分答案通过此题。

既然使用二分，我们首先要做的就是确定边界：我们假设左鞋和右鞋各自有一只，分别为 1 和 1000000000，它们的丑陋值是 999999999，即二分的上限；我们再假设左鞋和右鞋各自同样有一只，分别为 1 和 1，它们的丑陋值是 0，即二分的下限。

接着套上二分模板。

Code

l=0;r=1e9;
while(l<r){
    mid=(l+r-1)/2;
    if(check(mid))r=mid;
    else l=mid+1;
}

Part2

有了二分的边界，就只剩下二分的判定了。

这里我用了双指针+贪心来实现。

先求出哪种鞋子少，用并进行标记，左鞋标 1，右鞋标 0。

再给左、右鞋子各自从小到大排序（贪心思想）。

接着就可以用双指针了，分成2类：

  第1类：左鞋和右鞋指针指向的一双鞋符合条件（不超过要判断的数），左鞋和右鞋指针同时加一，组成的鞋子数量加一；  
  第2类：左鞋和右鞋指针指向的一双鞋不符合条件（超过要判断的数）指向鞋子数量多的指针加一；

最后判断组成的鞋子数是否达到要求即可。

Code

bool check(int x){
    int t=1,w=1,s=0;
    while(t<=n&&w<=m)
        if(abs(a[t]-b[w])<=x)t++,w++,s++;
        else if(flag)w++;//flag为标记
            else t++;
    return s==cnt;//cnt为要求的鞋子数
}

最后贴上完整代码

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,flag,i,a[100010],b[100010],l,r,mid;
bool check(int x){
    int t=1,w=1,s=0;
    while(t<=n&&w<=m)//双指针
        if(abs(a[t]-b[w])<=x)t++,w++,s++;
        else if(flag)w++;
            else t++;
    return s==cnt;
}
int main(){
    scanf("%d%d",&n,&m);
    cnt=min(n,m);//求出要求达到鞋子数
    if(cnt==n)flag=1;//进行标记
    else flag=0;
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    for(i=1;i<=m;i++)scanf("%d",&b[i]);
    sort(a+1,a+1+n);sort(b+1,b+1+m);//贪心
    l=0;r=1e9;
    while(l<r){//二分
        mid=(l+r-1)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%d",r);
}

求过