hdu1394Minimum Inversion Number树状数组求逆序对水题
发布时间：2020-12-13 20:15:10 所属栏目：PHP教程 来源：网络整理
导读：//ans[i]=ans[i⑴](n1)⑵*num[i] //num[i]为输入时的数据 //ans[i]为m=i时的逆序数 //用树状数组求ans[0]的逆序对 #includeiostream #includecstdio #includecstring using namespace std; const int maxn=5010; int num[maxn]; int tree[maxn]; int lowbit(i
|
//ans[i]=ans[i⑴]+(n+1)⑵*num[i] //num[i]为输入时的数据 //ans[i]为m=i时的逆序数 //用树状数组求ans[0]的逆序对 #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=5010; int num[maxn]; int tree[maxn]; int lowbit(int i) { return i&(-i); } int getsum(int i) { int sum=0; while(i>0) { sum+=tree[i]; i-=lowbit(i); } return sum; } void update(int i,int dx) { while(i<maxn) { tree[i]+=dx; i+=lowbit(i); } } int main() { int n;int i; while(scanf("%d",&n)!=EOF) { memset(tree,sizeof(tree)); int ans[maxn]; memset(ans,sizeof(ans)); for(i=1;i<=n;i++) { scanf("%d",&num[i]); num[i]++; ans[0]+=(i⑴)-getsum(num[i]); update(num[i],1); } int sum=ans[0]; for(i=1;i<=n;i++) { ans[i]=ans[i⑴]+(n+1)⑵*num[i]; sum=min(ans[i],sum); } printf("%d ",sum); } } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |