1 solutions

  • 0
    @ 2021-11-9 19:46:17

    分治法

    把大问题化成小问题逐个解决,可以优化算法复杂度(局部的优化有利于全局,一个问题的解决,其影响力扩大了k倍,即扩大到了全局)。

    • 归并排序

    (1)分解(2)求解子问题,对子序列排序(3)合并

     

    和交换排序相似,但合并两个有序的子序列效率更高。

     就是比较两个子序列,得到的数存到另一个数组里。(とても簡単です)

     

    排序是竞赛中的常用功能,一般直接使用STL的sort()函数,并不需要自己再写一个排序的程序。不过也有一些特殊的问题,需要写出程序,并在程序内部做一些处理,例如逆序对问题。

     

     k=0直接暴力求有多少个逆序对,然后你就快快乐乐地TLE了。

    在子序列里元素都是有序的,不存在逆序对,逆序对只存在于不同的子序列之间。

    如果前一个子序列元素比后面元素大,就会产生逆序对。(注意产生的逆序对个数不止一个:cnt+=mid-i+1)

     

    当k不等于0时,又分两种情况:

    (1)cnt<=k,总逆序对交换次数<k,那么最少的逆序对数量为0.

    (2)cnt>k,k次交换都发生在逆序的相邻数上,那么剩余的逆序对是cnt-k。

     

    放代码:

    #include<iostream>
    #include<algorithm>
    #include<stdio.h>
    using namespace std;
    

    const int N=1e5+5; typedef long long ll; ll a[N],b[N],cnt;</p>

    void merge(ll l,ll mid,ll r){ ll i=l,j=mid+1,t=0; while(i<=mid&&j<=r){ if(a[i]>a[j]){ b[t++]=a[j++]; cnt+=mid-i+1; } else b[t++]=a[i++]; } while(i<=mid){ b[t++]=a[i++]; } while(j<=r){ b[t++]=a[j++]; } for(i=0;i<t;i++){ a[l+i]=b[i]; } }</p>

    void mergesort(ll l,ll r){ if(l<r){ ll mid=(l+r)>>1; mergesort(l,mid); mergesort(mid+1,r); merge(l,mid,r); } }</p>

    int main(){ ll n,k; int t; scanf("%d",&t); while(t--){ cnt=0; scanf("%lld %lld",&n,&k); for(ll i=0;i<n;i++){ scanf("%lld",&a[i]); } mergesort(0,n-1); if(cnt<=k) printf("0\n"); else printf("%lld\n",cnt-k); } return 0; }
    </p>

    逆序对除了可以用归并,还可以用树状数组求解,感兴趣的同学可以去了解一下。

    ps:还是不太理解的详见博客https://www.cnblogs.com/Untergehen/p/14315892.html

     

    EOF

    Information

    ID
    151
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    7
    Tags
    # Submissions
    66
    Accepted
    15
    Uploaded By