1 solutions
-
0
分治法
把大问题化成小问题逐个解决，可以优化算法复杂度（局部的优化有利于全局，一个问题的解决，其影响力扩大了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
- 1
Information
- ID
- 151
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 66
- Accepted
- 15
- Uploaded By
-
Untergehen