Balanced Photo
提交数: 7, 通过率: 85.71%, 平均分: 85.71
题目描述:
Farmer John is arranging his N cows in a line to take a photo (1≤N≤100,000). The height of the iit
h cow in sequence is hihi, and the heights of all cows are distinct.As with all photographs of his c
ows, FJ wants this one to come out looking as nice as possible. He decides that cow ii looks "unbala
nced" if Li and RRi differ by more than factor of 2, where LiLi and RiRi are the number of cows tall
er than i on her left and right, respectively. That is, ii is unbalanced if the larger of Li and Ri
is strictly more than twice the smaller of these two numbers. FJ is hoping that not too many of his
cows are unbalanced.Please help FJ compute the total number of unbalanced cows.
农夫约翰正在安排他的N头牛拍照片， 每头牛有一个身高，从1到N编号，排列成一行(h1,h2...hn)，每头牛i左边
比他高的牛的数量记为Li，右边比他高的牛的数量记为Ri，如果存在i满足max(Ri,Li)>2*min(Li,Ri)则这个牛i是
不平衡的，现在FJ需要你告诉他有多少头牛不平衡。
输入格式:
The first line of input contains N. The next NN lines contain h1…hN
each a nonnegative integer at most 1,000,000,000.
输入第一行为N(N<=1e5)，接下来的一行有N个数，每个数表示第i头牛的身高，不超过1e9
输出格式:
Please output a count of the number of cows that are unbalanced.
输出有多少头牛是不平衡的
样例输入:
7 34 6 23 0 5 99 2
样例输出:
3
提示:
在这个样例中，身高为34，5,2的牛是不平衡的
时间限制: 1000ms空间限制: 128MB
来源: Usaco2017 Jan Gold