关于排序的稳定性和Hack

这道题的话有一个明显的观察就是交换同一列中两根高度相同的火柴是没有意义的。因此按大多题解的做法，排序后要使逆序对最少，是应该先按值排序、再按下标排序。

但是注意到题解给出的代码中基本写的都是只按值调用了 std::sort()，但这个函数提供的是不稳定排序，也就是说值相同的元素在排好序后不一定是保持原相对顺序的。所以答案可能就会不对，这里提供一组 Hack 数据：

PLAIN

17  
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

标准输出应该是 0，在洛谷在线 IDE 环境下应该是能 Hack 掉现在所有的 CPP 题解。

如果这在你的本地测试 Hack 不生效，可能是因为你的编译器使用的是 libc++ 标准库而不是 libstdc++，对 std::sort() 函数的实现有所不同。可以试试这个：

PLAIN

31
0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 4 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 3 31

标准输出仍应是 0（似乎在长度在 30 及以下的排序中，libc++ 的 sort 都是稳定的）。

那么解决办法就是换成双关键字排序或者用 std::stable_sort() 排序。实际上该这么做是显然的，但考虑到题解基本都比较古早可能当时注意到这一点的人不多。现在的选手是被期望意识到这个问题的。

讨论操作