地址:http://acm.hdu.edu.cn/showproblem.php?pid=4911
题意:可以进行k次相邻数的交换,问交换后还有多少个逆序对。
解析:
两种 nlog(n)的做法:
一:
归并排序
直接套模板即可。
归并排序,两次递归后,得到的是内部已经排好序的两组,所以只要有一个a[i]>a[j],那么前一部分所有数都>a[j],sum+=md-i+1.
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int maxn=1e5+10; int a[maxn],c[maxn]; ll ans=0; void merge_sort(int l,int r) { if(l>=r) return ; int md=(l+r)>>1; merge_sort(l,md); merge_sort(md+1,r); int i=l,j=md+1; int k=0; while(i<=md&&j<=r) { if(a[i]<=a[j]) c[k++]=a[i++]; else { c[k++]=a[j++]; ans+=md-i+1; } } while(i<=md) c[k++]=a[i++]; while(j<=r) c[k++]=a[j++]; for(i=l,j=0;i<=r;i++,j++) a[i]=c[j]; } int main() { int n; ll kk; while(~scanf("%d%lld",&n,&kk)) { ans=0; for(int i=0;i<n;i++) scanf("%d",&a[i]); merge_sort(0,n-1); if(ans-kk<=0) cout<<"0"<<endl; else cout<<ans-kk<<endl; } }
二:
树状数组
数据达到了1e9,开1e9的数组很明显不现实。
所以需要离散化:
for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+1+n); int len=unique(b+1,b+1+n)-(b+1);
这个操作,使得b[]的前len个,为a[]去重后的结果。
这样数据就可以用离散化后的坐标来代替。开1e5就可以了。
getsum(i),求得是,加入i个数,它之前比它小的数有多少个,那么i-getsum(i),就是比它大的数有多少个了,即为逆序对数。
lowber_bound找到第一个>=a[i]的位置id,id~maxn都要+1,
对于它们来讲,出现在他们之前的比它们小的数的数目+1,自然的,getsum(i)就是询问的比它小的数,一减,就是逆序对数了。
sum爆long long 了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int maxn = 1e5+10; int a[maxn]; int n,k; int b[maxn]; int c[maxn]; int lowbit(int x) { return x&(-x); } void update(int id,int x) { for(int i=id;i<maxn;i+=lowbit(i)) { c[i]+=x; } } int getsum(int id) { int ans=0; for(int i=id;i>0;i-=lowbit(i)) ans+=c[i]; return ans; } int main() { while(~scanf("%d%d",&n,&k)) { // memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+1+n); int len=unique(b+1,b+1+n)-(b+1); ll sum=0; for(int i=1;i<=n;i++) { int id=lower_bound(b+1,b+1+n,a[i])-b; update(id,1); sum+=i-getsum(id); } if(sum<k) cout<<"0"<<endl; else cout<<sum-k<<endl; } }