信友队数据万岁!

与上贴相对,信友队数据万岁!

当然,这个帖子不是夸张信友队数据,而是让数据变得不水!

当然,如果我算错了,那就是信友队数据万岁!

image
image
看着两个题面,明显 n,m \le 10^5 ,基本上写题的话得要 O(n\,log\,n)O(n) 才能解。

而我这个聪明的人成功写了一个 O(nm) AC掉!!!

#include <bits/stdc++.h>
using namespace std;
struct node{
  int x,y;
}x[100005];
struct node2{
  int x,y;
}y[100005];
int a[100005];
int main(){
  int n,m,s;
  cin>>n>>m>>s;
  for(int i=1;i<=n;i++){
    cin>>x[i].x>>x[i].y;
  }
  for(int i=1;i<=m;i++){
    cin>>y[i].x>>y[i].y;
  }
  for(int i=1;i<=n;i++){
  	int p=x[i].x,q=x[i].y;
  	int minn=s+1;
  	for(int j=1;j<=m;j++){
	  int p2=y[j].x,q2=y[j].y;
	  //cout<<p<<" "<<q<<" "<<p2<<" "<<q2<<endl;
	  int as=max(abs(p2-p),abs(q2-q));
	  minn=min(minn,as);
	}
	a[i]=minn;
	//cout<<minn<<" ";
  }
  int ans=-1;
  for(int i=1;i<=n;i++){
  	ans=max(ans,a[i]);
  }
  cout<<ans;
}

dalao如果我算错了跟我说一下,我立刻就删!!!

昨天我们寒假智灵班做了一个题:
局部截取_20250126_194223
就离谱
但是答案最多只有 10^{18}

那是因为剪枝了()

不是,是因为根本不需要用到那么多,也不用什么搜索剪枝,O(n)就能解决, n\le10^6 ,空间复杂度也才O(n)

我的意思是类似于括号匹配的处理方式把这堆东西处理完了hh

然而实际上我的代码里连高精度都没出现过