自动搬运

查看原文

来自洛谷，原作者为

	FZY_CZY 对于人生而言，重要的不是凯旋，而是奋斗

搬运于2025-08-24 22:53:22，当前版本为作者最后更新于2024-10-25 20:12:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题是在老师举办的 CSP-J 的模拟赛上见到的，赛上寄了，没写出来，痛定思痛，决定写着一篇题解。

题意就不赘述了，不懂的看这里：题目。

其实一开始我是想打暴力的，但是不会打。

后来想到了正解，结果打不出来。（也就是浅浅想了一个小时而已）

首先讲思路，思路很简单，就是对于每一个奶牛做一条它方向的射线，然后对于一条射线上没有任何交点的奶牛来说，它可以无限吃下去。

首先我们要去判断 $AO$ 与 $BO$ 的位置关系，第一步，不能使 $AO$ $\parallel$ $BO$，因为明显的，$AO$ 和 $BO$ 不能平行；然后对于每一个交点（这里统一称为 $O$ 点）：若 $AO>BO$ 则 $B$ 点在 $O$ 点时会停下；反之亦然。特别需要注意的是，若 $AO=BO$ 则不会停下。（由题意可得）

为了压缩时间复杂度保证当前奶牛的停止位置是在正确的位置（即遇到的第一个空地），我们需要进行排序（这个只是单独提出来，没必要说太多了）然后进行遍历，一次保证答案的正确性，这个就没什么多说的了，主要的思路大概就这么多了，剩下零碎的看代码注释。

#include<bits/stdc++.h>
#define maxn 55
using namespace std;
struct node{
	int x,y,id;
};//结构体方便排序和处理
node N[maxn],E[maxn];
int sum_n,sum_e,ans[55];
bool cmp1(node a, node b)
{
	return a.x<b.x;
}
bool cmp2(node a, node b)
{
	return a.y<b.y;
}
int main(){
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		char c;
		int x,y;
		scanf(" %c%d%d",&c,&x,&y);//输入
		if (c=='N') N[++sum_n]={x,y,i};
		else E[++sum_e]={x,y,i};
	}
	sort(N+1,N+sum_n+1,cmp1);
	sort(E+1,E+sum_e+1,cmp2);
	//排序后可以减时间复杂度并且简化代码
	for (int i=1;i<=sum_e;i++)
	{
		for (int j=1;j<=sum_n;j++)//双重for，没什么好说的
		{
			if (N[j].x<E[i].x) continue;//如果这两条射线不相交就不存在交点O
			if (N[j].y>E[i].y) continue;//同上
			int A=N[j].x-E[i].x;
			int B=E[i].y-N[j].y;
			if (ans[N[j].id]) continue;//如果N[j]已经有答案，那么这就是最优的了（排过序）
			if (A<B) ans[N[j].id]=B;//如果AO<BO则B是A的答案
			if (A>B)
			{
				ans[E[i].id]=A;//同理
				break;//第一个即最优解，没必要继续遍历
			}
		}
	}
  //值得一提的是，不需要两次双for，因为在找E的最优解的时候，也找到了N的最优解，所以只需要一次双for就OK了（我模拟赛就是疯了，写了两次，而且都写错了）
	for (int i=1;i<=n;i++)
	{
		if (ans[i]) printf("%d\n",ans[i]);//奶牛会适量进食
		else printf("Infinity\n");//奶牛会吃撑死
	}
	return 0;
}