自动搬运

查看原文

来自洛谷，原作者为

	WsW_ 欢迎入群872763867||题解求赞！题解看不懂请私信

搬运于2025-08-24 23:06:48，当前版本为作者最后更新于2024-12-02 17:58:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

上位黄，非 STL 的模拟题。

思路

对于每个教练，其他教练对他来说都相当于障碍，所以在输入教练的时候直接把所有教练同时加到障碍里面。

对于每个教练，我们考虑他能发现几个人在摸鱼。
因为只有 $k$ 个维度，所以每个教练最多只能往 $2k$ 个方向看。因为往每个方向看的时候，只能看见离自己最近的人，所以最多只能发现 $2k$ 个人在摸鱼。

首先预处理出每个方向上里教练最近的障碍。
接着，对于每个学生，判断他在这个方向上到教练的距离是不是比障碍到教练的距离更近。如果不是，那不用管这个学生；如果是，那么这个学生成了这个方向上新的障碍，且这个方向上离教练最近的是学生。
以上过程中记得判断障碍或学生是不是有且仅有 $k-1$ 维和教练不同。

最后统计有几个方向上离教练最近的是学生即可。

时间复杂度 $O\left(y(m+x+y)\times k\right)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
int n,k,m,x,y;
int a[maxn][5],b[2*maxn][5],c[maxn][5];
int tag[2][5];//存储每个方向上到教练最近的障碍
bool vis[2][5];//标记每个方向上到教练最近的是不是学生

void work(int p){
	int ans=0;
	memset(tag[0],0,sizeof(tag[0]));
	memset(tag[1],0x7f,sizeof(tag[1]));
	memset(vis,0,sizeof(vis));//初始化
  
	for(int i=1;i<=x;i++){//预处理障碍
		int scnt=0,dif=-1;//scnt记录有几个维度不同；dif记录不同的是哪个维度
		for(int j=1;j<=k;j++){
			if(b[i][j]!=c[p][j])dif=j;
			else scnt++;
		}
		if(scnt!=k-1)continue;//不满足，直接跳过
		if(b[i][dif]<c[p][dif])tag[0][dif]=max(tag[0][dif],b[i][dif]);
		else tag[1][dif]=min(tag[1][dif],b[i][dif]);
	}
  
	for(int i=1;i<=m;i++){//对每个学生进行处理
		int scnt=0,dif=-1;
		for(int j=1;j<=k;j++){
			if(a[i][j]!=c[p][j])dif=j;
			else scnt++;
		}
		if(scnt!=k-1)continue;
		if(a[i][dif]<c[p][dif]&&a[i][dif]>tag[0][dif]){
			tag[0][dif]=a[i][dif];
			if(!vis[0][dif]){
				ans++;
				vis[0][dif]=1;
			}
		}
		if(a[i][dif]>c[p][dif]&&a[i][dif]<tag[1][dif]){
			tag[1][dif]=a[i][dif];
			if(!vis[1][dif]){
				ans++;
				vis[1][dif]=1;
			}
		}
	}
	cout<<ans<<' ';//遍历vis，求其中有几个1也可
}

int main(){
	cin>>n>>k>>m>>x>>y;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=k;j++)
			cin>>a[i][j];
	for(int i=1;i<=x;i++)
		for(int j=1;j<=k;j++)
			cin>>b[i][j];
	for(int i=1;i<=y;i++)
		for(int j=1;j<=k;j++){
			cin>>c[i][j];
			b[x+i][j]=c[i][j];//教练相当于障碍
		}
	x+=y;//障碍数要加上教练数
	for(int i=1;i<=y;i++)
		work(i);
	return 0;
}