P2994题解

· · 题解

理解题意：

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

题目中的奶牛进入餐厅和座位的四个变量，两两一组是直角坐标系里的 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;
}