小贝的收音器讨论

常规
1

这个仅仅是讨论，ok！

4 个赞
2

？？？

3 个赞
3 
#include<bits/stdc++.h>
using namespace std;
int n,m,s,a[10000001][2],b[10000001][2],c[1001][1001],ans;
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;++i){
		cin>>a[i][0]>>a[i][1];
	}
	for(int i=1;i<=m;++i){
		cin>>b[i][0]>>b[i][1];
	}
	while(1){
		memset(c,0,sizeof(c));
		for(int i=1;i<=n;++i){
			++c[a[i][0]][a[i][1]];
		}
		int t=0;
		for(int i=1;i<=m;++i){
			for(int j=b[i][0]-ans;j<=b[i][0]+ans;++j){
				for(int k=b[i][1]-ans;k<=b[i][1]+ans;++k){
					if(j>=1&&j<=s&&k>=1&&k<=s){
						if(c[j][k]==1){
							c[j][k]=0;
							++t;
						}
					}
				}
			}
		}
		if(t==n){
			cout<<ans;
			break;
		}
		++ans;
	}
	return 0;
}
3 个赞
4

二分+二维差分+二维前缀和，O(s^2logs)的，考场写的就是正解

4 个赞
6 
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,s,max=0,num=0,l,r,mid;
	cin>>n>>m>>s;
	int ax[n],ay[n],bx[m],by[m];
	for(int i=0;i<n;i++)
	{
		cin>>ax[i]>>ay[i];
		if(ax[i]>max) max=ax[i];
		if(ay[i]>max) max=ay[i];
	}
	for(int i=0;i<m;i++)
		cin>>bx[i]>>by[i];
		l=0;r=max;
	while(l<r)
	{
		mid=l+r>>1;
		num=0;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
			{
				if(abs(ax[i]-bx[j])<=mid&&abs(ay[i]-by[j])<=mid)
				{
					num++;
					break;
				}
			}
		if(num<n) l=mid+1;
		else r=mid;
	}
	cout<<l;
	return 0; 
}

前面代码有点笨，主要是二分,套3个循环TLE

3 个赞
7 
#include<bits/stdc++.h>
using namespace std;
int n,m,s;
struct xx{
	int x,y;
};
xx a[1000001];
xx b[1000001];
bool v[1001][1001];
bool f(int z){
	bool bbj=0;
	for(int i=1;i<=n;i++){
		bool sbj=0;
		for(int j=1;j<=m;j++){
			if(a[i].x<=b[j].x+z&&a[i].x>=b[j].x-z){
				if(a[i].y<=b[j].y+z&&a[i].y>=b[j].y-z){
					sbj=1;
					break;
				}
			}
		}
		if(sbj==0){
			bbj=1;
			break;
		}
	}
	if(bbj==0) return 1;
	else return 0;
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	for(int j=1;j<=m;j++){
		scanf("%d%d",&b[j].x,&b[j].y);
	}
	int l=0,r=s,mid;
	while(l<r){
		mid=(l+r)/2;
		if(f(mid)==1) r=mid;
		else l=mid+1;
	}
	cout<<l;
	return 0;
}
3 个赞