AcWing 1215. 小朋友排队(python树状数组解法)
原题链接
中等
#贪心:只要不出现两个数字交换两次及以上,就算贪心。(冒泡排序)
#逆序对个数<=>冒泡排序交换次数
'''
证明:
①每次进行冒泡排序过程中,每次交换必然会使逆序对数量恰好减少1.
②冒泡排序结束时,逆序对数量一定为0.冒泡排序还未进行时,逆序对数量也应为k
'''
#逆序对个数一定是对应最小情况
'''
证明:
①每个小朋友为了能够到达最优解,那么ta一定会将与ta之前比ta大的交换,ta之后比ta小的交换
②将所有小朋友的k1与k2求和,我们不难得出其正好为两倍逆序对数量,因此所有小朋友最好的交
换方式即为k次交换,恰好冒泡排序正好能实现k次交换
'''
#题目简化为①求逆序对数量(归并排序)②利用树状数组求ta之前比ta大的所有数字
#写法一:树状数组(注:树状数组必须下标由1开始)
def lowbit(x):
return x&-x
def add(i,c):
while i < N:
tr[i] += c
i += lowbit(i)
return
def query(t):
res = 0
while t > 0:
res += tr[t]
t -= lowbit(t)
return res
if __name__ == "__main__":
N = 1000100
tr = [0] * N#树状数组,数组中存放的基础值为在该数组下表下对应相同身高的小朋友的人数
sums = [0] * N#存放每个小朋友的交换次数
res = 0
n = int(input())
h = list(map(int,input().split()))
for i in range(n):
h[i] += 1 #注意树状数组下标必须从1开始
#计算在每个小朋友之前比ta高的人的个数
for i in range(n):
sums[i] = query(N-1)-query(h[i])
add(h[i],1)
tr = [0]*N#清空树状数组
#计算每个小朋友之后比ta低的人的个数
for i in range(n-1,-1,-1):
sums[i] += query(h[i]-1)
add(h[i],1)
for i in range(n):
res += (1+sums[i])*sums[i]/2
print(int(res))