先放上我的惨烈提交界面

题目链接

解题思路

nodeee于2020/8/20退役
这道题目写的我看了几篇OI退役的文章，在想该怎么写。。。

作为一道二分，其实无非就是枚举。最开始我的思路是二位前缀和，结果一次爆空间，离散化后爆时间。。。于是重构了一次代码。尝试用尺取法做，虽然说思路是正确的，但是在中间有一个对于x的判重会导致错误，我也不会改。。。于是又重构了一次代码。这次我学聪明了，看了一篇题解，对着上边写，感觉不对的地方就自己写，又调了两个小时，发现题解是对的，终于过了。这题基本上就是对了第二个点第七个点错，改完第七个第一个点错，改完第一个第八个点错，改完第八个第三个点错。。循环往复~
历时：8h

本题是对于x排序，然后在每一个x的极限区间中找y是否超过mid即可。其中找最大最小y可以直接sort。（我也不知道为啥，明明可能爆时间的。。。）

代码

#include<bits/stdc++.h>
using namespace std;
int c,n;
struct pos{
    int x,y;
}p[505];
bool cmp(pos aa,pos bb){
    if(aa.x==bb.x)return aa.y<bb.y;
    return aa.x<bb.x;
}
int yy[505];
bool check(int l,int r,int mid){
    for(int i=l;i<=r;i++){
        yy[i-l+1]=p[i].y;
    }
    sort(yy+1,yy+(r-l+1)+1);
    for(int i=c;i<=(r-l+1);i++){//对于每一对y进行判断。 
        if(yy[i]-yy[i-c+1]+1<=mid)return 1;
    }
    return 0;
}
bool isok(int mid){
    int ll=1;
    for(int i=1;i<=n;i++){
        int can=0;
        if(p[i].x-p[ll].x+1>mid){//如果超过或将要超过mid，则取到长度最大值，可以开始判定，并且i不可取，所以i-1 
            if(i-ll+1>=c){//区间长度足够 
                can=check(ll,i-1,mid);
            }
        }
        if(can)return 1;
        while(p[i].x-p[ll].x+1>mid)ll++;
    }
    if(p[n].x-p[ll].x+1<=mid){//防止没有超过mid但是正好和mid相等的情况 
        if(n-ll+1>=c){
            if(check(ll,n,mid))return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&c,&n);
    int maxn=0;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&p[i].x,&p[i].y);
        maxn=max(maxn,max(p[i].x,p[i].y));
    }
    sort(p+1,p+1+n,cmp);
    int l=0,r=maxn+1,mid;
    while(l+1<=r-1){
        mid=(l+r)>>1;
        if(isok(mid)){
            r=mid;
        }else{
            l=mid;
        }
    }
    printf("%d",r);
    return 0;
} 

本文链接：http://kaispace.com.cn/index.php/archives/695/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者