题解：P9957 [USACO20DEC] Stuck in a Rut B

· · 题解

这道题是在老师举办的 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;
}