【题目描述】给定一个序列
。若i
;,则。请你写一个程序,在尽量短的时间内统计出"逆序对“的数目。
【输入格式】第1行是整数n ( 1≤n<500000),接下来1行,n个整数。【输出格式】一个整数,为逆序对的数目。
【输入样例】
6
5 4 2 6 3 1【输出样例】
11
5后面有4个数比它小,所以5和这四个数是4个逆序对,4后面有三个比它小的数,2后面有一个比它小的数,以此类推,从左到右依次检查每个数右边比它本身小的数的数量,然后相加,4+3+1+2+1=11,就可以得到所有逆序对的数量。
模拟:先检查第一个数a,把后面所有数跟它比较,如果发现有一个比a,小,就是一个逆序对;再检查第二个数,第三个数......;直到最后一个数。
【代码】:
n =int(input ())
a = list(map (int, input().split()))
res = 0
for i in range(n):for j in range(i+1, n):if a[j]
复杂度:。本题n最大为
,暴力法超时了
观察暴力法的执行过程,发现和交换排序很像。
能否用交换排序的升级版归并排序,来处理逆序对问题?
归并排序:
对n个数进行归并排序:
观察归并排序的一次合并过程,发现能利用这个过程来记录逆序对。
逆序对只存在于不同的子序列之间。
如果前一个子序列的元素比后面子序列的元素小,无逆序对。
如果前一个子序列的元素比后面子序列的元素大,有逆序对,且有mid-(i-1)个
【代码】:
def merge(L, mid, R):global resi = L;j = mid+1;t=0while(i <= mid and j <= R):# 左半边和右半边有一个到边界就结束if(a[i] > a[j]):b[t] = a[j]; t+=1;j+=1 # 如果前一个子序列的元素比后面子序列的元素大,有逆序对,且有mid-(i-1)个res = res + mid-i+1 #记录逆序对数量else: b[t] = a[i]; t+=1;i+=1 # 如果前一个子序列的元素比后面子序列的元素小,无逆序对。
#一个子序列中的数都处理完了,另一个还没有,把剩下的复制过来while i <= mid: b[t]=a[i];t+=1; i+=1while j <= R:b[t]=a[j];t+=1 ;j+=1for i in range(t): a[L+i] = b[i]#把排好序的b[]复制回给a[]def merge_sort(L, R): # 分治if L
优点:复杂度
缺点:存在大量拷贝,增加了时间成本;代码不如用树状数组简单。
用树状数组求逆序对,是树状数组的巧妙应用,比其他方法都好。
用树状数组解逆序对:把数字看成树状数组的下标。
例如序列{5,4,2,6,3,1},对应a[5]、a[4]、a[2]、a[6]、a[3]、a[1]。
每处理一个数字,树状数组的下标所对应的元素数值加一,统计前缀和,就是逆序对的数量。
①倒序
用树状数组倒序处理数列,当前数字的前一个数的前缀和即为以该数为较大数的逆序对的个数。
例如{5,4,2,6,3,1},倒序处理数字:
复杂度:处理n个数字,每个数字有加一add()和求前缀和sum()操作(都是logn),所以总复杂度为O(nlogn)
②正序(虽然正序比较难,但也可能需要用到,例如下面例题)
当前已经处理的数字个数减掉当前数字的前缀和即为以该数为较小数的逆序对个数。
例如{5,4,2,6,3,1},正序处理数字:
上面的处理方法“把数字看成树状数组的下标”有个问题,如果数字比较大,例如数字等于,那么树状数组的空间也要开到
= 1G,远远超过了题目限制的空间。
用“离散化”这个小技巧能解决这个问题。
离散化方法1:重复数字离散化后不一样
a = [1,20543,19,376,546007640,19]
print(a)
b = sorted(a)
print(b)
for i in range (len(b)):k = a.index(b[i])a[k] = i+1 #a[a.index(b[i])]= i+1
print(a) # [1,5,2,4, 6,3]
离散化方法2:重复数字离散化后也一样
def discretization(h):b = list (set (h)) # 用集合去重b. sort()for i in range (len(h)) :h[i] = b.index(h[i])+1
a = [1,20543,19,376,546007640,19]
print(a)
discretization(a) # 列表可以在函数中完成修改且不需要return
print (a) # [1,4,2,3,5,2]
【代码】:
# 数组树状标准模板
def lowbit(x):return x & -x
def update(x, d):while x <= n:tree[x] += dx += lowbit(x)
def sum(x):ans = 0while(x > 0):ans += tree[x] x -= lowbit(x)return ansn = int(input())
a = [0]+list(map(int,input ().split()))#从a[1]开始
# 离散化
b = sorted(a)
for i in range(n+1) : a[a.index (b[i])] = i+1tree = [0]*(n+1)
res = 0
for i in range(len(a)-1, 0, -1):update(a[i], 1)res += sum(a[i]-1)
print (res)
题目描述
n个小朋友站成一排。现在要把他们按身高从低到高的顺序排列,但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。开始的时候,所有小朋友的不高兴程度都是 0。
如果某个小朋友第一次被要求交换,则他的不高兴程度增加 1,如果第二次要求他交换,则他的不高兴程度增加 2(即不高兴程度为 3),依次类推。当要求某个小朋友第 k 次交换时,他的不高兴程度增加 k。
请问,要让所有小朋友按从低到高排队,他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样,则他们谁站在谁前面是没有关系的。
输入描述
输入的第一行包含一个整数 n,表示小朋友的个数。
第二行包含 n 个整数 H1H2...Hn,分别表示每个小朋友的身高。
其中,
。
输出描述
输出一行,包含一个整数,表示小朋友的不高兴程度和的最小值。
输入输出样例
输入
3 3 2 1
输出
9
每一个小朋友最少的交换次数等于他左边比他高的人数加上右边比他矮的人数。
(1)他左边比他高的人;
(2)右边比他矮的人。
N = 100010
def discret(sl: list): #树状数组离散化(离散化方法2:重复数字离散化后也一样)hl = sorted(set(sl))for i in range(len(sl)):sl[i] = hl.index(sl[i]) + 1tree = [0] * N
def lowbit(x):return x & (-x)
def tree_add(x, d):while x <= N:tree[x] += dx += lowbit(x)
def tree_sum(x):ans = 0while x > 0:ans += tree[x]x -= lowbit(x)return ansn = int(input())
a = list(map(int, input().split()))
discret(a) #对n个小朋友的身高进行离散化(究竟是什么样的小朋友身高会是1e6)
a = [0] + a#每个人交换次数=前面比他高的人数+后面比他矮的人数
excnt = [0] * N #记录n个小朋友每人交换的次数,0不用
for i in range(1, n + 1): #正向统计,可以计算出a[i]前面比a[i]高的人数tree_add(a[i], 1)excnt[i] = i - tree_sum(a[i])tree = [0] * N #重新初始化tree数组
for i in range(n, 0, -1): #逆向统计,可以计算出a[i]后面比a[i]矮的人数tree_add(a[i], 1)excnt[i] += tree_sum(a[i] - 1) #统计和res = 0
for i in range(1, n + 1): #统计总的不高兴值res += excnt[i] * (1 + excnt[i]) // 2 #n次交换,不高兴值是1+2+3+...+n
print(res)