一道算法题

  1. 10月前
    10月前Sakura 重新编辑

    原帖地址
    一个单链表,每个节点里存储都是正整数,现在是无序的,可能会有重复数字,可以修改每个节点里的值,达到以下两个目标:

    [1] 单链表变为有序的,从大到小,可以大于等于.
    [2] 修改的△值最小.

    举例:

    1.单链表 2->4->1->3 ,可能改为 3->3->1->1 此时,此时链表有序,此时的△ = |(2 - 3)| + |(4 - 3)| + |(1 - 1)| + |(3 - 1)| = 4. 或者可以改为 2->2->2->2 此时的△ = |(2 - 2)| + |(4 - 2)| + |(1-2)| + |(3-2)| = 4.
    2.单链表 1->19->2 ,可能改为 2->2->2,△ = 1 + 17 + 0 = 18.

    这个题目的n太小了,如果把n变成1000000的话你就会发现时间上完全过不去。
    我们考虑一个递减序列,假如想让他满足条件是不是我们只需要把所有数都变成中位数就可以了,并且满足答案最优。
    于是我们有了一个简单的想法:设w[i]表示第i段的中位数,我们把序列分成m段,只要满足中位数不递减就好了,那么我们假设我们现在处理的是第i个数字,我们把它单独变成一段,假如加上这一段一共有m段的话,假如a[i]<w[m-1],我们就把这个数合并到上一段里面,然后去维护这一段的中位数,事实上你可以看成我们把一段变成了一个数,这个数是这一段的中位数,现在我们就是要考虑维护中位数,怎么维护呢?
    我们只需要一个大根堆,如果这个堆得元素个数>n/2,n为这一段的元素个数,那么我们就把堆顶弹掉,那么我们现在需要的就是合并两个大根堆,上左偏树即可。

  2. 先说说我目前的思路
    可以先以所有数的平均值为一个基准,在这个基准上面进行调整,但我暂时还想不出来怎么做

  3. 我们拿左偏树维护一下中位数就好了

  4. @ypxrain 我们拿左偏树维护一下中位数就好了

    可以详细说明一下吗

  5. 10月前Sakura 重新编辑

    https://blog.csdn.net/guhaiteng/article/details/52739135
    看到了一个示例,应该不难读懂

  6. ypxrain

    6楼 2018年3月29日 被采纳

    这个题目的n太小了,如果把n变成1000000的话你就会发现时间上完全过不去。
    我们考虑一个递减序列,假如想让他满足条件是不是我们只需要把所有数都变成中位数就可以了,并且满足答案最优。
    于是我们有了一个简单的想法:设w[i]表示第i段的中位数,我们把序列分成m段,只要满足中位数不递减就好了,那么我们假设我们现在处理的是第i个数字,我们把它单独变成一段,假如加上这一段一共有m段的话,假如a[i]<w[m-1],我们就把这个数合并到上一段里面,然后去维护这一段的中位数,事实上你可以看成我们把一段变成了一个数,这个数是这一段的中位数,现在我们就是要考虑维护中位数,怎么维护呢?
    我们只需要一个大根堆,如果这个堆得元素个数>n/2,n为这一段的元素个数,那么我们就把堆顶弹掉,那么我们现在需要的就是合并两个大根堆,上左偏树即可。

 

后才能发言