有一个点怎么样答过不去 是我的做法假了还是我哪里的小细节出问题了?
#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;
}
答案:7539
我的输出:7540