JZOJ_7.17C组第一题 乱头发节/洛谷P2866 糟糕的一天Bad Hair Day

本文主要是介绍JZOJ_7.17C组第一题 乱头发节/洛谷P2866 糟糕的一天Bad Hair Day，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出n头牛的身高。它们都往右边看，只有high[i]>high[j]的情况下，i牛才能看到j牛的头发，如果i牛被挡住了，那么它就看不见后面的牛了。现在我们要求出每只牛可以看见的牛的头发的数量的总和。

思路

一个方向而且有大小限制，我们就可以想到使用单调栈。每次待入栈的牛的身高要和栈顶判断，弹到栈顶<待入栈的牛的身高，之后让答案累加上tot-1，tot代表栈的长度，因为栈里的前tot-1个都是单调递减的，它们都能看到新加上来的牛。

代码

#include<cstdio>
long long ans;//答案要开longlong，不然会炸
int stack[80001],n,a,tot;
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&a);while (a>=stack[tot]&&tot>=1) tot--;stack[++tot]=a;ans+=tot-1;}printf("%lld",ans);
}

这篇关于JZOJ_7.17C组第一题 乱头发节/洛谷P2866 糟糕的一天Bad Hair Day的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---