• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1804 – Brainman

    ACM-POJ EXP 196阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    POJ2299 一摸一样,区别在于数据规模缩小了而已

    解题思路

    重申一次要点:

    一个乱序序列的 逆序数 = 在只允许相邻两个元素交换的条件下,得到有序序列的交换次数


    这题有两种解法

    ① 若想通过借助归并排序求逆序数:时间复杂度O(nlogn)

     可以参看我 POJ2299 的思路,几乎一模一样的程序,不过由于规模的缩小,全部变量用int即可

    ② 也可以直接求逆序数,无需借助归并排序:时间复杂度O(n^2)

     把S[i]和s[i+1~n]的元素逐个比较,如果s[i] > s[k] (k∈[i+1,n]) 则逆序数t++


    方法一:归并排序

    转载请注明:EXP 技术分享博客 » POJ1804 – Brainman

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

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