自动搬运

查看原文

来自洛谷，原作者为

	yinhy09 既然选择了远方，便只顾风雨兼程~

搬运于2025-08-24 21:44:12，当前版本为作者最后更新于2021-11-19 12:19:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

理解题意：

我第一次看这道题的时候，没理解输入数据，所以在这里解释一下:

题目中的奶牛进入餐厅和座位的四个变量，两两一组是直角坐标系里的 $X,Y$ 轴 因为这个题最多 $1000\times1000$（$m,n\leq1000$ )所以直接暴力枚举！

那么问题又来了，到底先枚举奶牛还是座位。也就是两层循环哪一个放在外面 当然是先枚举座位，即外层循环是枚举座位，内层循环枚举奶牛。因为每一个奶牛不一定有座位，但是每一个座位一定有奶牛。

本题可以定义四个数组储存变量，但是这里可以优化一下，只定义两个数组，剩下两个直接定义成普通变量。因为座位可以每输入一个进行一次奶牛查找（判断哪一个奶牛）放在同一个 for 循环中，具体见下方代码:

代码示例：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+5;//为了方便定义数组，直接把数据范围控制好
long long a[maxn],b[maxn],c,d;//a,b表示奶牛计入房间位置，c,d表示座位位置
int flag[maxn];//用来标记那些奶牛已经有座位了
int pos;//记录有座位的奶牛编号
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	for(int j=1;j<=m;j++)
	{
		cin>>c>>d;
		long long dis=0;//计算当前奶牛到座位的距离，用勾股定理（因为只需要比较，所以没有开根号）
		long long mindis=1e15;//记录当前最小奶牛距桌子距离（开始随便赋值，大一些）
		for(int i=1;i<=n;i++)
		{
			if(flag[i]==1)continue;//已有座位，直接跳过
			dis=(a[i]-c)*(a[i]-c)+(b[i]-d)*(b[i]-d);//计算距离，用勾股定理
			if(dis<mindis)//如果刷新了最小纪录
			{
				mindis=dis;//重新赋最小值
				pos=i;//标记
			}
		}
		flag[pos]=1;//标记，已有座位
	}
	if(n==m)//特判没有奶牛无座位
	{
		cout<<0;
		return 0;
	}
	for(int i=1;i<=n;i++)//其他情况输出
	{
		if(flag[i])continue;
		cout<<i<<endl;
	}
	return 0;
}