【题解】Corral the Cows
先放上我的惨烈提交界面
题目链接
解题思路
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/
如果未注明出处,复制公开后需将注明本博客链接。打赏作者