我正在 www.hackerrank.com 上做一个问题，我已经被困了好几天了。
这是问题的陈述https://www.hackerrank.com/challenges/insertion-sort 。基本上，我必须计算给定数组在 O(nlog(n)) 时间内插入排序中发生了多少次交换。
http://paste.ubuntu.com/12637144/这是我提交的代码。我使用合并排序并计算每个元素被移位的次数。该代码通过了网站一半以上的测试。当它失败时，它不会超时，并且不会出现编译错误或段错误。
此外，当我获得一个失败的测试用例的输入(这是在网站 http://paste.ubuntu.com/12637165/ 上失败的输入)并使用我的代码的这个变体 http://paste.ubuntu.com/12637127/ 对其进行测试时它实际上运行插入排序算法，计算一路上的交换次数，并将其与合并排序计数进行检查，我通过了所有测试。另外，我生成了数千个随机测试用例，它们也都通过了这个测试。
我认为这不是网站的问题，因为在对该问题的讨论中，其他人似乎很好地通过了测试，没有任何问题或投诉。所以也许我误解了这个问题，或者我只是写了错误的算法和算法的测试用例。有人有什么建议吗？
最佳答案
如果 n 可以达到 100000，则 no。反转的次数可以是 ~= n^2/2 ，这不适合 32 位整数。尝试使用 64 位整数进行计数和归并排序的返回值。
关于c - 这个倒数计数算法的实现有什么问题呢？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32904026/