当前位置: 代码迷 >> 综合 >> HDU 1394 Minimum Inversion Number(线段树/归并排序求逆序对数)
  详细解决方案

HDU 1394 Minimum Inversion Number(线段树/归并排序求逆序对数)

热度:77   发布时间:2023-12-08 11:12:52.0

题目链接:
HDU 1394 Minimum Inversion Number
题意:
给出一组数,可以将每个数组首的数依次移到数组尾,求整个过程中(包括初始状态)的最少逆序对数。
分析:

  • 用线段树求初始数组的逆序对数。对每个读入的数在线段树中查询之前有多少比它大的数字出现,那么这就是该数的逆序对数,累加就是整个初始数列的逆序对数。然后将读入的数插入到线段树叶子结点中,(指该数字已经出现了),线段树中需要记录区间已经出现数字个数。对于每个从数列首移到数列尾的移动,可以用 tmp+=((n?1?a[i])?a[i]) ;表示。对于每一个后移的

  相关解决方案