AcWing 1215. 小朋友排队(python归并排序解法)
原题链接
中等
#贪心:只要不出现两个数字交换两次及以上,就算贪心。(冒泡排序)
#逆序对个数<=>冒泡排序交换次数
'''
证明:
①每次进行冒泡排序过程中,每次交换必然会使逆序对数量恰好减少1.
②冒泡排序结束时,逆序对数量一定为0.冒泡排序还未进行时,逆序对数量也应为k
'''
#逆序对个数一定是对应最小情况
'''
证明:
①每个小朋友为了能够到达最优解,那么ta一定会将与ta之前比ta大的交换,ta之后比ta小的交换
②将所有小朋友的k1与k2求和,我们不难得出其正好为两倍逆序对数量,因此所有小朋友最好的交
换方式即为k次交换,恰好冒泡排序正好能实现k次交换
'''
#题目简化为①求逆序对数量(归并排序)②利用树状数组求ta之前比ta大的所有数字
#写法二:归并排序
class student:
def __init__(self):
self.height = 0
self.idx = 0#记录上次的位置
self.rank = 0
def merge_sort(l,r):
if l >= r: return
mid = l + r >> 1
merge_sort(l,mid)
merge_sort(mid+1,r)
i,j = l,mid+1
k = l
while i <= mid and j <= r:
if stu[i].height <= stu[j].height:
tmp[k].height = stu[i].height
tmp[k].idx = stu[i].idx
tmp[k].rank =stu[i].rank
i += 1
k += 1
else:
tmp[k].height = stu[j].height
tmp[k].idx = stu[j].idx
tmp[k].rank =stu[j].rank
k += 1
j += 1
while i <= mid:
tmp[k].height = stu[i].height
tmp[k].idx = stu[i].idx
tmp[k].rank =stu[i].rank
i += 1
k += 1
while j <= r:
tmp[k].height = stu[j].height
tmp[k].idx = stu[j].idx
tmp[k].rank =stu[j].rank
k += 1
j += 1
for p in range(l,r+1):#将排好序的数组还原给原数组
stu[p].height = tmp[p].height
stu[p].idx = p
stu[p].rank = tmp[p].rank + abs(tmp[p].idx - p)#只需要记录在这一段排完序前后该数字交换的距离就可以计算出其在这个区间中的逆序对数量
return
if __name__ == "__main__":
N = 100010
tmp = [student() for i in range(N)]
sums = [0]*N
n = int(input())
nums = list(map(int,input().split()))
stu = [student() for i in range(N)]
for i in range(n):
stu[i].height = nums[i]
stu[i].idx = i
stu[i].rank = 0
merge_sort(0,n-1)
res = 0
for i in range(n):
res += (1+stu[i].rank)*stu[i].rank/2
print(int(res))