解题思路:
注意事项:
参考代码:
n=int(input())
h=list(map(int,input().split()))
maxh=max(h)
cnt=[0]*(n)
c=[0]*(maxh+2)#c[i]代表的是身高i-1
def lowbit(i):
return i&(-i)
def update(i,num):
while(i<=maxh+1):
c[i]+=num
i+=lowbit(i)
def getsum(i):#计算的是原始数组[0,i]的和
sum=0
while(i>0):
sum+=c[i]
i-=lowbit(i)
return sum
for i in range(n):#左边要统计比它大的
update(h[i]+1,1)
sum=getsum(h[i]+1)
cnt[i]+=i+1-sum
c=[0]*(maxh+2)
for i in range(n-1,-1,-1):
update(h[i]+1,1)
sum=getsum(h[i])
cnt[i]+=sum
ans=0
for i in range(len(cnt)):
ans+=((1+cnt[i])*cnt[i]//2)
print(ans)
0.0分
2 人评分
【密码】 (C语言代码)浏览:333 |
C语言考试练习题_排列 (C语言代码)浏览:725 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:886 |
WU-字符串比较 (C++代码)浏览:758 |
核桃的数量 (C语言代码)浏览:671 |
IP判断 (C语言代码)浏览:539 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:686 |
简单的a+b (C语言代码)浏览:512 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:508 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:471 |