今日题解 - 博客 - 贾永菁的博客

今日题解

2022-05-27 19:33:08 By 贾永菁

这一题不怪大家不会主要是一看标签就腿软

归并排序树状数组离散化递归！！！

你瞧瞧，您看看，这还是人做的玩意儿？

大家都学过归并排序吧，一句话分而治之

俗一点讲，就是先把这个数组切碎，碎成渣渣的那种，再给他拼到一起。

摘自——小马语录

逆序对呢，只要在他碎成渣渣拼着的时候看一下

A渣渣队：5 6 7 8

B渣渣队：1 2 3 4

先拿B队的第一个跟A队的第一个比1 < 5对不对

所以就有4个逆序对

发现加的是序列中点的下标-当前A队下标+1

可能还没理解

贴个代码

int i=l,j=m+1,k=0;   //i为当前队首下标，j是也就相当于这个队列切一半分出的第二个队列的队首下标，k是合出的新队列的元素个数兼下标

while(i<=m&&j<=h)

{

    if(a[i]>a[j])    如果a[i]>a[j]  j默认是>i的

        b[k++]=a[j++],ans+=m-i+1;      设队列为 3  4  1  2 m=1，则ans+加了1-0+1  是不是正好加了2 

    else

        b[k++]=a[i++];

}

上面的是归并代码中的一部分

归并完全代码自己想

OK完事儿

又是自律的一天

xushuoxin

到头来，就是归并排序呗

2022-05-27 21:57:28
回复

xushuoxin

看来还很简单的

2022-05-27 22:07:42
回复

xukailing3

It's no wonder that everyone won't be weak at the sight of the label Merge sort tree array discretization recursion!!! Look, look, this is still a human thing? Everyone has learned to merge and sort. In a word, divide and rule As the saying goes, it's the kind of array that is first cut into bits and pieces, and then put them together. Excerpt - quotations from pony The reverse order is right. Just look at it when he's broken into bits and pieces A slag team: 5678 B slag team: 1234 Take the first of team B and the first of team a first than 1 < 5, right So there are four pairs in reverse order It is found that the subscript at the midpoint of the sequence is added - the current subscript of team a +1 May not understand Post a code

2022-07-02 14:45:11
回复

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。