Bad Hair Day

Love The Way You Lie 2022-08-18 02:30 103阅读 0赞

## Bad Hair Day ##

####  ####

##### Time Limit: 2000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

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－－＞  
＝　　　＝　　　＝  
＝　＝　＝　＝　＝  
＝　＝　＝　＝　＝　＝  
１　２　３　４　５　６  
  
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 c1 through cN.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.

## 输入 ##

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.

## 输出 ##

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

## 示例输入 ##

6
    10
    3
    7
    4
    12
    2

## 示例输出 ##

## 来源 ##

USACO 2006 November Silver

#include <stdio.h>  
    int main()  
    {  
        int n, i, j, count;  
        int a[80000];  
        while (scanf("%d", &n) == 1)  
            {  
            for (i=0; i<n; i++)  
                scanf("%d", a+i);  
            count = 0;  
            for (i=0; i<n; i++)  
            {  
                for (j=i+1; j<n; j++)  
                    if (a[j] >= a[i]) break;  
                count += j-i-1;  
            }  
            printf("%d\n", count);  
        }  
        return 0;  
    }