Some of Farmer John's N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows' heads.
Each cow i has a specified height hi (1 ≤ hi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.
Consider this example:
Cow#2 can see no cow's hairstyle
Cow#3 can see the hairstyle of cow #4
Cow#4 can see no cow's hairstyle
Cow#5 can see the hairstyle of cow 6
Cow#6 can see no cows at all!
Let ci denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c1 through cN.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.
http://bbezxcy.iteye.com/blog/1413892
http://www.hankcs.com/program/algorithm/poj-3250-bad-hair-day.html
Read full article from 3250 -- Bad Hair Day
Each cow i has a specified height hi (1 ≤ hi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.
Consider this example:
= = = = - = Cows facing right --> = = = = - = = = = = = = = = 1 2 3 4 5 6Cow#1 can see the hairstyle of cows #2, 3, 4
Cow#2 can see no cow's hairstyle
Cow#3 can see the hairstyle of cow #4
Cow#4 can see no cow's hairstyle
Cow#5 can see the hairstyle of cow 6
Cow#6 can see no cows at all!
Let ci denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c1 through cN.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.
http://bbezxcy.iteye.com/blog/1413892
一排共n头牛排队站在一起，给出队伍中每头牛的高度。每头牛只能看到站在他右边且个头比他小的牛。求出所有牛可以看到的牛数之和。
题目大意：有一群牛站成一排，每头牛都是面朝右的，每头牛可以看到他右边身高比他小的牛。给出每头牛的身高，要求每头牛能看到的牛的总数。
本题还有一个类似的题，那就是给出N块竖直的木板的高度，现在在第 i 块木板的右方加水，问可以水可以淹没多少木板。
思路：也就是说针对每只牛，啊，不，每头牛求它到它右边第一个比它高（或身高相等）的牛之间有多少头牛，然后将求得的结果相加就是最后的答案。朴素的做法是针对每头牛去寻找右边比它高的牛的位置，时间复杂度为O(n^2)，如果用单调栈的话就是O(n).
具体实现：利用根据单调递增栈解决，如果栈为空或入栈元素小于栈顶元素则入栈，否则会破坏栈的单调性，则将栈顶元素出栈并更新结果，直到栈为空或碰到一个小于入栈元素的值。然后将当前元素入栈。
设数组的最后一个元素为最大值，也就相当于在最右边的牛的右边设了一个高度无限高的牛。这样做的目的是，最后让栈内的元素全部出栈。
PS：我的代码中的单调栈保存的是牛的位置。
int i,n,top,a[80010]; //top指向栈顶元素
LL ans; //存储最终结果
stack<int> st; //st为栈，每次入栈的是每头牛的位置
while(~scanf("%d",&n))
{
while(!st.empty()) st.pop(); //清空栈
for(i=0;i<n;i++)
scanf("%d",&a[i]);
a[n]=inf; //将最后一个元素设为最大值
ans=0;
for(i=0;i<=n;i++)
{
if(st.empty()||a[i]<a[st.top()])
{ //如果栈为空或入栈元素小于栈顶元素，则入栈
st.push(i);
}
else
{
while(!st.empty()&&a[i]>=a[st.top()])
{ //如果栈不为空并且栈顶元素不大于入栈元素，则将栈顶元素出栈
top=st.top(); //获取栈顶元素
st.pop(); //栈顶元素出栈
//这时候也就找到了第一个比栈顶元素大的元素
//计算这之间牛的个数，为下标之差-1
ans+=(i-top-1);
}
st.push(i); //当所有破坏栈的单调性的元素都出栈后，将当前元素入栈
}
}
printf("%lld\n",ans);
}
题解：很基础的一个单调栈思想题，如样例，10,3,7,4,12,2.因为左边的牛i可以看到右边第一个大于等于他的牛j区间（I,J）中的所有牛，所以我们可以声明一个栈，维护从大到小的值。
.....................1.首先把10放进栈中。
......................2.看3，因为3<10，所以可以把3放入栈中。
......................3.看7，因为7>栈首元素3，所以把3从栈中pop，在弹出的时候，可以知道有多少头牛可以看到高度为3的牛的头呢？当然就是所有留在栈中的元素个数。
......................4.4可以直接入栈。
......................5.12大于栈首元素，所以不断弹栈，直到栈为空或者栈首元素大于当前值为止。
注意最后一个值操作完之后，栈不一定为空，此时的栈是一个元素单调递减的栈，所以里面满足的个数有（sz-1）*(sz)/2.
分析:首先要有一个转换的思想,如果先计算每只奶牛可以看到的奶牛数,再加起来,那么复杂度就是O(n^2),但是如果我们换一个idea,把求所有奶牛可以看到的其他奶牛之和转化为所有奶牛可以被多少头奶牛看到的数量之和.这两个问题是等价的,这样,整个问题就比较好解决了,复杂度也降低了很多(略大于O(n)),从左到右扫一遍奶牛的高度,用一个栈保存前i-1头奶牛中可以被第i头奶牛看到的数量,然后每次统计一下,计算和.
while( ~scanf("%d",&n))
{
for( int i = 0; i < n; i++)
scanf("%d",&h[i]);
//要求每头牛可以看到的牛的数量之和
//可以转化为每头牛可以被多少头牛看到的数量
ans = 0;
stack<int> s;
for( int i = 0; i < n; i++)
{
while( !s.empty() && s.top() <= h[i])
s.pop();
ans += s.size();
s.push(h[i]);
}
printf("%lld\n",ans);
}
大致思路：
做到poj3415，居然碰到“单调栈”这种牛逼的玩意，于是专门来把这道题切掉。所谓单调栈也就是每次加入一个新元素时，把栈中小于等于这个值的元素弹出。接下来回到这道题。求所有牛功能看到多少牛，可以转化为：这n头牛共能被多少头牛看见。当我们新加入一个高度值时，如果栈中存在元素小于新加入的高度值，那这个牛肯定看不见这个高度的牛，就把这个元素弹出。每次加入新元素，并执行完弹出操作后，栈中元素个数便是可以看见这个牛的“牛数”~~~。
- stack<long long>sta;
- int main(){
- long long num,n,i,ans;
- while(scanf("%lld",&n)!=EOF){
- ans=0;
- scanf("%lld",&num);
- sta.push(num);
- for(i=1;i<n;i++){
- scanf("%lld",&num);
- while(!sta.empty()&&sta.top()<=num){
- sta.pop();
- }
- ans+=sta.size();
- sta.push(num);
- }
- printf("%lld\n",ans);
- while(!sta.empty())sta.pop();
- }
- return 0;
- }
http://www.hankcs.com/program/algorithm/poj-3250-bad-hair-day.html
两种思路，第一种是All nearest smaller values的逆问题，即找到最近的greater or equal值，将两者下标做差。
scanf("%d", &N);
for (int i = 0; i < N; ++i)
{
scanf("%d", h + i);
}
stack<int> sta;
long long ans = 0;
for (int i = N - 1; i >= 0; --i)
{
for (; !sta.empty() && h[sta.top()] < h[i]; sta.pop());
ans += (sta.empty() ? N : sta.top()) - i - 1;
sta.push(i);
}
printf("%lld\n", ans);
另一种是转换思路，求每个人头能被几个人看到。明显只能被比自己高的人看到，用一个严格单调递增的栈维护比自己高的人的身高，将栈的大小累加即得到最终答案。
是poj 2796的弱化版Read full article from 3250 -- Bad Hair Day
