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

    ACM-POJ EXP 153阅读 0评论

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


    题目大意

    给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。


    解题思路

    一看就是冒泡,交换一次记录一次就可以了

    但是n的范围达到50W,冒泡O(n^2)的复杂度铁定超时(即使有7000ms,其实这是一个陷阱

    直接用快排又不符合题目的要求(相邻元素交换),快排是建立在二分的基础上的,操作次数肯定比在所要求的规则下的交换次数要更少

    那么该怎么处理?

    其实这题题目已经给出提示了:Ultra-QuickSort

    特殊的快排,能和快排Quicksort相媲美的就是归并排序Mergesort了,O(nlogn)

    但是用归并排序并不是为了求交换次数,而是为了求序列的 逆序数(学过《线代》的同学应该很熟悉了)

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


    例如例子的

    9 1 0 5 4

    由于要把它排列为上升序列,上升序列的有序就是 后面的元素比前面的元素大

    而对于序列9 1 0 5 4

    9后面却有4个比9小的元素,因此9的逆序数为4

    1后面只有1个比1小的元素0,因此1的逆序数为1

    0后面不存在比他小的元素,因此0的逆序数为0

    5后面存在1个比他小的元素4, 因此5的逆序数为1

    4是序列的最后元素,逆序数为0

    因此序列9 1 0 5 4的逆序数 t=4+1+0+1+0 = 6 ,恰恰就是冒泡的交换次数


    PS:注意保存逆序数的变量t,必须要用__int64定义,int和long都是无法保存的。。。。会导致WA。 以前的long long 在现在的VC编译器已经无法编译了。

    注意__int64类型的输出必须使用指定的c格式输出,printf(“%I64d”,t);

    cout是无法输出__int64类型的

    序列数组s[]用int就足够了,每个元素都是小于10E而已

    转载请注明:EXP 技术分享博客 » POJ2299 – Ultra-QuickSort

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

    表情

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

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