题解 P7150 【[USACO20DEC] Stuck in a Rut S】

· · 题解

P7150 题解

思路

经过一段时间，每头奶牛的身后会留下一条被啃秃了的轨迹。

这一句给了我们很关键的提示：奶牛的轨迹是一条线

所以可以将奶牛根据行进方向的不同分成两类

因为所有的奶牛的x，y坐标都不相同。

意味着向北走的奶牛只会被向东走的奶牛阻挡，向东走的奶牛只会被向北走的奶牛阻挡。

那么如何判断每头奶牛阻挡的个数呢？

观察数据范围发现：只可能从奶牛的行进方向入手（因为x,y的取值过大）。 所以我们可以将每一头奶牛的路径“画出来”。但是这样还是不能避免涉及过多坐标的问题。所以还需要精简。

考虑奶牛什么时候会停下：当且仅当方向不同且已行进路程的两头奶牛相遇时，才会有一头奶牛停下。所以我们可以

维护交点

是的，只需要维护每头牛走过的线的交点即可。所以现在重点就是如何记录交点以及交点需要存储哪些信息。

首先我们要考虑哪些奶牛可以产生交点。

产生交点的条件：

  1. 两头奶牛的方向不同
  2. 假设向东走的奶牛为c_e,向北走的奶牛为c_n，则奶牛要相遇的条件为
c_e.x < c_n.x

且

c_e.y > c_n.y

这个结论很好推，因为对于c_n，它的x坐标是不变的，所以如果一开始c_e的x坐标就比c_n大，那么很显然不能交上，y坐标同理

现在我们已经有了一张偌大的图，图上有若干个交点，那么我们应该维护哪些信息呢？

假设现在有一个交点P,由两头牛N,E相交得到，那么我们现在要判断哪一头牛会被挡住，只需判断两头牛起始点距交点的距离即可（很显然距离大的会被挡住）。

所以交点维护的信息已经一目了然：

交点坐标，由哪两条线相交而来（存储线的编号）。

但现在又有一个问题了：有的牛会被挡住，它实际上只走了一个线段，但是我们存储的仍然是一条射线。

这个问题其实很好解决，我们可以设置一个删除数组，维护每一头牛有没有被挡住，那么在交点判断时，如果有牛被挡住了，很显然这个交点是不存在的。 那么对于没有被挡住的牛，他挡住的牛的个数应该是

他本身挡住的牛的个数 + 他挡住的另一头牛挡住的牛的个数 + 1（另一头牛本身）

最后一个问题：判断交点顺序

相交距离越小的点越先被判断。那么哪些点的距离比较小呢？

很显然是左下角的点（因为牛是往右或者上走的）。

所以我们要对交点进行排序，以x坐标和y坐标的任意一个作为第一关键字排序,另一个作为第二关键字排序（从小到大），然后判断交点即可。

接下来上代码：

#include <bits/stdc++.h>
#define ll long long
#define ri register int
using namespace std;
struct cows{
    int x,y,num;
}c[1100],nth[1100],est[1100];//结构体维护奶牛的信息
//x，y为坐标，num为输入的编号（因为之后要把奶牛存到两个数组里去）
//nth数组是向北走的奶牛的集合，est是向东的 
struct point{
    int x,y;
    int numx,numy;
    bool operator < (const point others) const
    {
        if(this->x  == others.x){
            return this->y < others.y;
        }
        return this->x < others.x;
    }//重载运算符，当然写比较函数也可 
}p[1100 * 1100 /4];//交点维护坐标和相交奶牛的编号 
int n,cntn,cnte,cntp,ans[1100];
bool del[1100];//删除数组 
int main(void)
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i = 1;i <= n;i++){
        char x;
        cows tmp;
        cin>>x>>tmp.x>>tmp.y;
        tmp.num = i;
        if(x == 'N'){
            c[i] = tmp;
            nth[++cntn] = tmp;
        }
        else{
            c[i] = tmp;
            est[++cnte] = tmp;
        }
    }//输入不解释 
    for(int i = 1;i <= cntn;i++){
        for(int j = 1;j <= cnte;j++){
            if(nth[i].x > est[j].x && nth[i].y < est[j].y){
                p[++cntp].x = nth[i].x;
                p[cntp].y = est[j].y;
                p[cntp].numx = est[j].num;
                p[cntp].numy = nth[i].num;
            }//建立交点 
        }
    }
    sort(p + 1,p + 1 + cntp);
    for(int i = 1;i <= cntp;i++){
        if(del[p[i].numx] || del[p[i].numy]){
            continue;//如果有一头牛被挡住，说明交点不存在了 
        }
        int dx = p[i].x - c[p[i].numx].x;
        int dy = p[i].y - c[p[i].numy].y;//计算距离 
        if(dx < dy){
            del[p[i].numy] = 1;
            ans[p[i].numx] = ans[p[i].numx] + ans[p[i].numy] + 1;
        }
        if(dx > dy){
            del[p[i].numx] = 1;
            ans[p[i].numy] = ans[p[i].numy] + ans[p[i].numx] + 1;
        }
    }
    for(int i = 1;i <= n;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}

蒟蒻第一次写题解，希望能过