蒟蒻求助
查看原帖
蒟蒻求助
308384
Morpheuse楼主2021/10/19 23:36

有一个点怎么样答过不去 是我的做法假了还是我哪里的小细节出问题了?

#include<bits/stdc++.h>
using namespace std;

#define maxn 100010

struct node
{
	int x , y;
}p1[maxn] , p2[maxn];
bool cmpy(node x , node y)
{
	if(x.y == y.y) return x.x < y.x;
	else return x.y < y.y;
}
bool cmpx(node x , node y)
{
	if(x.x == y.x) return x.y < y.y;
	return x.x < y.x;
}

int n;

int ups , downs , upl , downr , y , uplx , downrx , upls , downls , uprs , downrs;;//上面和 下面和 上面左 下面右 横着栅栏

bool ok(int pdowns , int  downs , int pups , int ups , int now)
{
	return (pdowns <= now && downs - pdowns <= now && pups <= now && ups - pups <=now) ? 1 : 0;
}

bool check(int now)
{
	uplx = 0 , downrx = p1[n].x;//指针位置
	upls = 1 , downls = 0 , uprs = n , downrs = 0; //左上和 左下和 右上和 右下和 
	ups = n , downs = 0 , upl = 1 , downr = n;//上面和 下面和 上面左扫到第几个点 下面右扫到第几个点 横着栅栏位置
	y = 0;
	int i = 0;
	while(i <= n)
	{
		while(upls < now && upl <= n)
		{//满足上面
			++ upl;
			if(p1[upl].y > y) upls ++;//在横着的栅栏上面 
			else downls ++;//在横着的栅栏下面
			
		}
		uplx = p1[upl].x;//记录当前指针位置
		
		while(downrs > now && downr >= 0)
		{
			-- downr;
			if(p1[downr + 1].y > y) -- uprs;
			else -- downrs;
		}
		downrx = p1[downr].x;
		
		if(ok(downls , downs , upls , ups , now) || ok(downrs , downs , uprs , ups , now)) return 1;
		
		do
		{
			++ i;//扫下一个 栅栏是否向上移动还需要判定 
			downs ++ , ups --;
			y = p2[i].y;//往上移动 如果相同就不移动 
	//		//cout<<p2[i].x<<"?"<<endl;
			if(p2[i].x <= uplx)
			{
				upls --;
				downls ++;
			}
			if(p2[i].x <= downrx)
			{
				uprs --;
				downrs ++;
			}
			if(ok(downls , downs , upls , ups , now) || ok(downrs , downs , uprs , ups , now)) return 1;
		}while(i + 1 <= n && p2[i].y == p2[i + 1].y);
	}
	return 0;
}

int main()
{
//	freopen("10.in" , "r" , stdin);
	scanf("%d", &n);
	for(int i = 1 ; i <= n ; ++ i)
	{
		scanf("%d%d", &p1[i].x,&p1[i].y);//1用于枚举横着的栅栏
		p2[i].x = p1[i].x , p2[i].y = p1[i].y;//2用于线段树竖着的栅栏 
	}
	sort(p1 + 1 , p1 + 1 + n , cmpx);
	sort(p2 + 1 , p2 + 1 + n , cmpy);
	int l = 0 , r = n , ans = INT_MAX;
	while(l < r)
	{
		int mid = (l + r) >> 1;
	//	//cout<<mid<<"!"<<endl;
		if(check(mid))
		{
			ans = min(mid , ans);
			r = mid;
		}
		else
			l = mid + 1;
	}
	printf("%d", ans);
	return 0;
}

input

答案:7539

我的输出:7540

2021/10/19 23:36
加载中...