【POJ 3250】牛的视野

曾经终败给现在 2021-12-03 15:59 162阅读 0赞

Bad Hair Day

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;25050</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;8525</td> 
  </tr> 
 </tbody> 
</table>

Description

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:

=
    =       =
    =   -   =         Cows facing right -->
    =   =   =
    = - = = =
    = = = = = =
    1 2 3 4 5 6

Cow\#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 *c*1 through *cN*.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.

Input

Line 1: The number of cows,  *N*.   
Lines 2..N+1: Line  *i*\+1 contains a single integer that is the height of cow  *i*.

Output

Line 1: A single integer that is the sum of  *c* 1 through  *cN*.

Sample Input

6
    10
    3
    7
    4
    12
    2

Sample Output

Source

[USACO 2006 November Silver][]

题解：计算每头牛可以看到牛的头数，可以等效于每头牛可以被看到的次数

从左到右依次读取当前牛的高度，从栈顶开始把高度小于或等于当前牛的高度的那些元素删除，此时栈中剩下的元素的数量就是可以看见当前牛的其他牛的数量，求和就是答案

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #include <stack>
    #include <string>
    #include <cmath>
    #include <cstdio>
    #include <functional> 
    typedef long long ll;
    #define N 1005
    using namespace std;
     
    int main()
    {
        int n;
        while(scanf("%d",&n)==1){
            int num;
            ll sum=0;
            scanf("%d",&num);
            stack<int>s;
            while(!s.empty())
                s.pop();
            s.push(num);
            for(int i=1;i<n;i++){
                scanf("%d",&num);
                while(!s.empty()&&num>=s.top()) //当前牛小于栈顶
                    s.pop();
                sum+=s.size();
                s.push(num);
            }
            printf("%lld\n",sum);
        }
        return 0;

转载于:https://www.cnblogs.com/wuhu-JJJ/p/11192414.html

[USACO 2006 November Silver]: http://poj.org/searchproblem?field=source&key=USACO+2006+November+Silver