Optimal Insertion(dfs/逆序对)

题目 题意：给定数组a和b，a相对位置不可动，b可以重新打乱顺序，插入到a数组中任意位置。求得到的新数组c，的最小逆序对。 官方题解 思路：要使逆序对最小，首先b数组必须为内部有序，所以需要对b数组进行预处理排序。插入到a数组的位置有n+1个。第i个位置表示插入在数 a i a_i ai​前，其中n+1表示插入在数 a n a_n an​后边。用 p o s i pos_i posi​表示 b i b_i bi​插入到 a i a_i ai​数组的新位置，由于b数组有序，所以有 p o s 1 < = p o s 2 < = , , , < = p o s m pos_1