请问为什么上面这段代码能AC
#include<bits/stdc++.h>
using namespace std;
int h,n,ans;
struct jgt
{
int x,y;
}zb[110];
bool cmp1(jgt a,jgt b)
{
return a.x<b.x;
}
int main()
{
scanf("%d%d",&h,&n);
if(n==0)
{printf("%d",h);return 0;}
for(int i=1;i<=n;i++)
scanf("%d%d",&zb[i].x,&zb[i].y);
zb[++n].x=0;zb[n].y=0;
zb[++n].x=0;zb[n].y=h+1;
zb[++n].x=h+1;zb[n].y=0;
zb[++n].x=h+1;zb[n].y=h+1;
sort(zb+1,zb+n+1,cmp1);
for(int i=1;i<=n;i++)
{
int x1=zb[i].x,up=h,down=0;
for(int j=i+1;j<=n;j++)
{
int x2=zb[j].x;
ans=max(ans,min(x2-x1-1,up-down-1));
if(zb[j].y>=zb[i].y)
up=min(up,zb[j].y-1);
else
down=max(down,zb[j].y-1);
}
}
for(int i=n;i>=1;i--)
{
int x1=zb[i].x,up=h,down=0;
for(int j=i-1;j>=1;j--)
{
int x2=zb[j].x;
ans=max(ans,min(x1-x2-1,up-down-1));
if(zb[j].y>=zb[i].y)
up=min(up,zb[j].y-1);
else
down=max(down,zb[j].y-1);
}
}
printf("%d ",ans);
return 0;
}
这段就只有20分
#include<bits/stdc++.h>
using namespace std;
int h,n,ans;
struct jgt
{
int x,y;
}zb[110];
bool cmp1(jgt a,jgt b)
{
return a.x<b.x;
}
int main()
{
scanf("%d%d",&h,&n);
if(n==0)
{printf("%d",h);return 0;}
for(int i=1;i<=n;i++)
scanf("%d%d",&zb[i].x,&zb[i].y);
zb[++n].x=0;zb[n].y=0;
zb[++n].x=0;zb[n].y=h+1;
zb[++n].x=h+1;zb[n].y=0;
zb[++n].x=h+1;zb[n].y=h+1;
sort(zb+1,zb+n+1,cmp1);
for(int i=1;i<=n;i++)
{
int x1=zb[i].x,up=h,down=0;
for(int j=i+1;j<=n;j++)
{
int x2=zb[j].x;
ans=max(ans,min(x2-x1-1,up-down-1));
if(zb[j].y>=zb[i].y)
up=min(up,zb[j].y);
else
down=max(down,zb[j].y);
}
}
for(int i=n;i>=1;i--)
{
int x1=zb[i].x,up=h,down=0;
for(int j=i-1;j>=1;j--)
{
int x2=zb[j].x;
ans=max(ans,min(x1-x2-1,up-down-1));
if(zb[j].y>=zb[i].y)
up=min(up,zb[j].y);
else
down=max(down,zb[j].y);
}
}
printf("%d ",ans);
return 0;
}
区别:更新上下边界时AC代码减了个1