T1是结论题吗?
  • 板块题目总版
  • 楼主_Archive_
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/11/19 13:06
  • 上次更新2023/10/27 02:24:28
查看原帖
T1是结论题吗?
484894
_Archive_楼主2022/11/19 13:06

我认为T1至少要两个,然后把点排序取右下半部分然后判断最上层和次上层有没有点遮挡,有的话分别+1,这样的结论错在哪里了?求指点

#include<bits/stdc++.h>
#define ll long long
#define pf(x) cout<<x<<endl;
#define ceshi cout<<"测试"<<endl;
//#pragma GCC optimize(2)
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
struct node{
	int x,y;
};
node t[100005];
bool cmp(node a,node b){
	if(a.y==b.y) return a.x>b.x;
	return a.y<b.y; 
}
vector<int>zb;
set<int>s;
int main(){
	int T=read();
	while(T--){
		int n=read();
		for(int i=1;i<=n;i++) t[i].x=read(),t[i].y=read(),s.insert(t[i].y);
		sort(t+1,t+n+1,cmp);
		int k1=0,k2=n/2;
		for(int i=n/2;i>=1;i--){
			if(t[i].y<t[k2].y){
				k1=i;
				break;
			}
		}
		bool f1=0,f2=0;
		for(int i=n/2+1;i<=n;i++){
			if(t[i].y>t[k2].y&&t[i].x>=t[k2].x){
				f2=1;
				break;
			} 
			if(t[i].y>t[k1].y&&t[i].y>=t[k1].y&&t[i].x>=t[k1].x) f1=1;
		}
		int ans=2+f1+f2;
		if(k1==k2) ans--;
		else if(k1==0) ans--;
		printf("%d\n",ans);
	}
	return 0;
}

2022/11/19 13:06
加载中...