题目描述:
给你一个数组a,a[i]可以加1或者不加,求进行所有操作完后最小的逆序对数
思路:
先把所有的逆序对数求出来,然后再找满足(a[i]>a[j]&&i<j&&a[i]==a[j]+1)条件的对数,再用所有的逆序对数减去满足条件对数就可以的出最小对数。
AC代码
#include<bits/stdc++.h> using namespace std; int num[200005]; int b[200005],ans[200005]; long long sum=0; void gbsort(int l,int r,int a[]) { int mid=(l+r)/2; if(l==r) return; else { gbsort(l,mid,a); gbsort(mid+1,r,a); } int i=l,t=l,j=mid+1; while(i<=mid&&j<=r) { if(a[i]>a[j]) { sum+=mid+1-i; b[t++]=a[j++]; } else { b[t++]=a[i++]; } } while(i<=mid) b[t++]=a[i++]; while(j<=r) b[t++]=a[j++]; for(int i=l;i<=r;i++ ) { a[i]=b[i]; } return; } int main() { int n; cin>>n; for(int i=0;i<n;i++){ cin>>ans[i]; num[ans[i]]=i; } gbsort(0,n-1,ans); for(int i=1;i<n;i++){ if(num[i]>num[i+1]){ sum--; i++; } } cout<<sum<<'\n'; return 0; }