传送门

推销博客

这里提供一种比较暴力的做法。

##算法分析：离散化+区间覆盖。

根据题意，Farmer John 能看到奶牛的时候奶牛恰好经过 $y$ 轴。显然，奶牛身体某部位在 $y$ 轴的时间是一个区间，可以考虑对时间轴进行区间覆盖，即将时间轴上 $st_i$ 到 $ed_i$ 这一段区间标记为 $i$，表示这段区间能看见的是第 $i$ 头奶牛。但是题目中数据范围很大，实际上并不能开那么大的数组，因此我们需要对时间点进行离散化。

##细节提示：

• 覆盖：当某一时间点已被覆盖，但新来的奶牛的 $y$ 值更小时，需要更新原先的覆盖。

• 离散化：离散化时，不能使用左闭右闭的形式，应当使用左闭右开，否则容易引起冲突（先排序再离散化！）。

比如说：第一只奶牛占据的时间是 $[1,2]$,$y=1$，第二只是 $[3,4]$,$y=1$，第三只是 $[2,3]$，$y=2$。显然的，前两只奶牛占据了 $[1,4]$ 这个区间，第三只奶牛所在区间已经被覆盖，并且第三只的 $y$ 值大于前两只（被挡住了）。但实际上，在第二秒结束时，第一只奶牛已经离开，第三只奶牛可以被看到。这样看来，左闭右闭的区间会引起冲突。因此，我们应当设置左闭右开区间，这样在覆盖时就不会引起冲突。

##code：

#include<bits/stdc++.h>
#define rd(n) scanf("%lld",&n);
#define F(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
const int N=4e5+10;
long long n,p,v,x;
long long st[N],ed[N],t[N];
int c[N],d[N],y[N];
int main() {
    rd(n)
    F(i,1,n) {
        rd(x)rd(y[i])rd(v)
        x++;
        x=-x;//将坐标转化为距离 
        st[i]=x*v;
        ed[i]=st[i]+v-1;
        t[++p]=st[i],t[++p]=ed[i];
        t[++p]=ed[i]+1;//左闭右开
    }
    memset(c,0x3f,sizeof(c));
    sort(t+1,t+p+1);//先排序再离散化 
    long long cnt=unique(t+1,t+p+1)-t-1;
    F(i,1,n) {
        st[i]=lower_bound(t+1,t+cnt+1,st[i])-t;//离散化 
        ed[i]=lower_bound(t+1,t+cnt+1,ed[i])-t;
        F(j,st[i],ed[i]){//暴力覆盖 
            if(c[j]>y[i]){//如果覆盖这一段时间的奶牛的 y 值大于现在的奶牛，就更新 
                c[j]=y[i];//c 模拟时间轴上奶牛的 y 值 
                d[j]=i;//d 记录时间轴上的奶牛编号 
            }
        }
    }
    int ans=0;
    F(i,1,n) {
        F(j,st[i],ed[i]) {
            if(d[j]==i){
                ans++;//如果第 i 头奶牛经过 y 轴的时间内能被看到，答案+1 
                break;
            }
        }
    }
    printf("%d",ans);
    return 0;
}

AC记录

欢迎交流讨论，请点个赞哦~