一点疑惑
查看原帖
一点疑惑
752711
hateful_bug楼主2024/9/11 17:54

请问为什么上面这段代码能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

2024/9/11 17:54
加载中...