题解 P2866 【[USACO06NOV]糟糕的一天Bad Hair Day】

· · 题解

Youngsc

大佬们都在统计一头牛能被几头牛看见，而蒟蒻在统计一头牛能看见几头牛。

我们可以倒着来扫，并同时维护一个单调栈，在每个元素入栈之前将身高小于它的全部出栈，然后如果栈里还有元素，那个这头牛一定是视野所及的最远的牛，也就是当视线的牛。因此栈顶的牛与当前的牛之间的牛均可被看见，累加进答案就好。如果栈里没有元素，那就说明一望无际，视线里的所有牛都能被看见，也将其累加进答案。

思路还是很好想的

代码在这里

# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <queue>
# include <cmath>
# define R register
# define LL long long

using namespace std;

int n,h[100010],st[100010],top;
LL ans;

inline void in(R int &a){
    R char c = getchar();R int x=0,f=1;
    while(!isdigit(c)){if(c == '-') f=-1; c=getchar();}
    while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
    a = x*f;
}

inline void maxx(R int &a,const int b){a>b? 0:a=b;}
inline void minn(R int &a,const int b){a<b? 0:a=b;}

inline int yg(){
    // freopen("maze1.in","r",stdin);
    // freopen("maze1.out","w",stdout);
    in(n);
    for(R int i=1; i<=n; ++i) in(h[i]);
    for(R int i=n; i>=1; --i)
    {
        while(top&&h[st[top]]<h[i]) top--;//将较小值都出栈。
        if(top) ans += st[top]-i-1;//站定挡住了视线，统计两个坐标之间
        else ans += n-i;//全能看见
        st[++top] = i;//入栈，此时进入的是坐标，以便接下来统计
    }
    printf("%lld",ans);
    return 0;
}

int youngsc = yg();
int main(){;}

（减少代码复制，共创美好洛谷）