【旧事重提】如何正确地排序
WeLikeStudying
·
2022-03-26 16:40:03
·
题解
我靠完全不会做，这个要注意。
主要的问题在于没有想到统计贡献的思想。
完全不会代码实现，这个也要注意，难道我已经连一维偏序也不会打了吗。
难道是因为我不会最快速的排序方法：bogo 排序吗？
民之从事，常于几成而败之；慎终如始，则无败事。
题意
题意。
给定一个 m\times n 的矩阵，求任意两列的和的最大值和最小值之和。
分析
啊，m=2 的情况容易解决，答案即为 O(n\sum a_{i,j})，代码。
对于 m=3 的情况，容易参变分离转化为二维偏序，也就是说：a_i+a_j\ge b_i+b_j 的情况可以转化为 a_i-b_i\ge b_j-a_j，所以问题可以理解成求 6 次二维偏序，这里对于去重的方面考虑可要仔细了，不过有大样例的话一般没什么问题，代码。
对于 m=4 的情况，难道要做 24 次三维偏序？并不一定，你看 m=2 的情况十分好算，我们枚举在中间的每种情况，然后减去它，代码。
怎么证明它是对的呢，如果不求甚解的话，枚举 4! 种可能的大小关系即可证明，但实际上，这种做法可以拓展到一般的情况，复杂度为 O(m!n\log n)。
实际上，原问题的本质是利用了这个结论：对于 1 到 m 的所有排列，使得第 i 个位置大于第 j 个位置，小于第 k 个位置（i,j,k 互不相等）的方案数一定是 n!/3!，可以利用概率分析证明，因此明确了这个结论，不仅可以写出简洁的代码，还可以拓展到一般的情况。
我们在信息学研究中，也应该对常见的问题进行总结和推广，不仅对自己有收获，更有可能丰富大众的思维。