[POJ2299]Ultra-QuickSort[逆序对,归并排序]

题面

题目求冒泡排序的最小交换次数.冒泡排序交换一次即减少一个逆序对,所以总交换次数就是逆序对数.用归并排序求出即可.

求逆序对通常用归并排序(树状数组也可以), 统计在两区间合并的过程中产生的逆序对就可以算上所有的逆序对, 因为归并排序实际上已经把整个数列的操作完美化为了许多最小子问题, 不会有重复和遗漏.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址