思路
1.求最小值的时候,可以直接按升序排序,这样得到的值就是最小值 2.求最小交换次数的时候,不能直接排序,因为只能交换相邻的数,只需要知道他们的相对大小,所以可以先用离散化,把火柴高度映射成 1 到 n,然后用一个中间数组 c,让 b 数组按照 a 数组的顺序归并排序,交换相邻两个元素,最多只会使得逆序对数量减一
#include#includeusing namespace std;const int N = 1e5 + 10, mod = 99999997;int a[N], b[N], c[N], d[N];int n;// 离散化 a 和 b 数组void init(int q[]){for(int i = 1; i