本文共 3076 字，大约阅读时间需要 10 分钟。
牛牛的作业薄上有一个长度为 n 的排列 A，这个排列包含了从1到n的n个数，但是因为一些原因，其中有一些位置（不超过 10 个）看不清了，但是牛牛记得这个数列顺序对的数量是 k，顺序对是指满足 i < j 且 A[i] < A[j] 的对数，请帮助牛牛计算出，符合这个要求的合法排列的数目。
每个输入包含一个测试用例。每个测试用例的第一行包含两个整数 n 和 k（1 <= n <= 100, 0 <= k <= 1000000000），接下来的 1 行，包含 n 个数字表示排列 A，其中等于0的项表示看不清的位置（不超过 10 个）。
输出一行表示合法的排列数目。
示例1
5 54 0 0 2 0
2
自己的方法：直接全排列，然后计算每个的顺序对数目，提交通过。
n,k=[int(each) for each in input().split()]arrs=[int(each) for each in input().split()]unused_arr=[i for i in range(1,n+1)]for i in arrs: if i in unused_arr: unused_arr.remove(i)import itertoolsunused_arr_ordered=[]for i in itertools.permutations(unused_arr): unused_arr_ordered.append(i)def getOrderedPairs(arrs): tmp_c=0 for i in range(n): for j in range(i,n): if arrs[i]
参考解法：
这种解法的解析参考代码中的注释，整体思路为，原始数组中的顺序对数+剩余数字产生的顺序对数+数字在每个位置的顺序对数
# 获取没有在输入数组中的数组，并且进行全排列，并且每个全排列内的顺序对数# 给出例子中为：[([1, 3, 5], 3), ([1, 5, 3], 2), ([3, 1, 5], 2), ([3, 5, 1], 1), ([5, 1, 3], 1), ([5, 3, 1], 0)]def gothrough(result, picked, rest): if len(rest) == 0: count = 0 for i in range(len(picked)): for j in range(i + 1, len(picked)): if picked[i] < picked[j]: count += 1 result.append((picked, count)) return else: for each in rest: nextpick = picked + [each] nextrest = rest - {each} gothrough(result, nextpick, nextrest) returnn, kk = [int(each) for each in input().split()]d = [int(each) for each in input().split()]# 获取不在d中的数字loss = list(set([i for i in range(1, n + 1)]) - set(d))# print(loss)# 获取d中为0的位置数目loss_p = []for i in range(n): if d[i] == 0: loss_p.append(i)# print(loss_p)# d中原始的顺序对数settlecount = 0for i in range(n - 1): if d[i] != 0: for j in range(i + 1, n): if d[i] < d[j]: settlecount += 1# print(settlecount)# 缺失的数字在每个对应位置时的顺序对数# 给出例子的结果为：{1: [1, 1, 0], 3: [0, 0, 1], 5: [1, 1, 2]}countonposition = {}# [[0 for i in range(len(loss_p))] for j in range(len(loss))]for i in range(len(loss)): count = 0 k = 0 countonposition[loss[i]] = [0 for _ in range(len(loss_p))] # 先从前到后 for j in range(n): if d[j] != 0: if d[j] < loss[i]: count += 1 else: countonposition[loss[i]][k] = count k += 1 if k == len(loss_p): break count = 0 k = len(loss_p) - 1 # 再从后向前遍历 for j in range(n - 1, -1, -1): if d[j] != 0: if d[j] > loss[i]: count += 1 else: countonposition[loss[i]][k] += count k -= 1 if k == -1: break# print(countonposition)self_result = []gothrough(self_result, [], set(loss))# print(self_result)possible = 0for picked, count in self_result: # print(picked, count) # 每种全排列本身的顺序对数，加上每个数字在对应位置产生的新的顺序对数 for i in range(len(picked)): count += countonposition[picked[i]][i] # 再加上原始d中的顺序对数 count += settlecount if count == kk: possible += 1 # print(picked)print(possible)
转载地址：http://ceyai.baihongyu.com/