??????
??? if(node[nd].left==node[nd].right) {node[nd].num++;return ;}?
?????
??? int mid=(node[nd].left+node[nd].right)/2;?
??? if(pos<=mid)? update(pos,nd*2);?
??? else update(pos,nd*2+1);?
??? node[nd].num=node[nd*2].num+node[nd*2+1].num;?
}?
int main()?
{?
??? int n,i,j;?
??? while(scanf("%d",&n)!=EOF)?
??? {?
????????? for(i=0;i ????????????? scanf("%d",&a[i]);?
????????? build(0,n-1,1);?
????????? int sum=0;?
????????? for(i=0;i ????????? {?
????????????? //printf("i=%d? sum=%d\n",i,sum);??
????????????? sum+=query(a[i],n-1,1);?
???????????? // printf(">>>");??
????????????? update(a[i],1);?
????????? }?
???????? // printf("%d\n",sum);??
????????? int ans=99999999;?
????????? if(ans>sum)? ans=sum;?
?????????? for(i=0;i ?????????? {?
?????????????? sum=sum-a[i]+n-1-a[i];?
?????????????? if(ans>sum) ans=sum;?
?????????? }?
?
?????????????? printf("%d\n",ans);?
??? }?
??? return 0;?
}?
#include
int a[10000];
struct haha
{
??? int left;
??? int right;
??? int num;
}node[10000*4];
void build(int left,int right,int nd)
{
??? node[nd].left=left;
??? node[nd].right=right;
??? node[nd].num=0;
??? if(left==right)
??? {
??????? return ;
??? }
??? int mid=(left+right)/2;
??? build(left,mid,nd*2);
??? build(mid+1,right,nd*2+1);
}
int query(int left,int right,int nd)
{
??? int mid=(node[nd].left+node[nd].right)/2;
??? if(node[nd].left==left&&node[nd].right==right)
??? {
??????? return node[nd].num;
??? }
??? if(right<=mid)
??? {
????????? return query(left,right,nd*2);
??? }
??? else if(left>mid)
??? {
??????? return query(left,right,nd*2+1);
??? }
??? else
??? {
??????? return query(left,mid,nd*2)+query(mid+1,right,nd*2+1);
??? }
}
void update(int pos,int nd)
{
????
??? if(node[nd].left==node[nd].right) {node[nd].num++;return ;}
???
??? int mid=(node[nd].left+node[nd].right)/2;
??? if(pos<=mid)? update(pos,nd*2);
??? else update(pos,nd*2+1);
??? node[nd].num=node[nd*2].num+node[nd*2+1].num;
}
int main()
{
??? int n,i,j;
??? while(scanf("%d",&n)!=EOF)
??? {
????????? for(i=0;i ????????????? scanf("%d",&a[i]);
????????? build(0,n-1,1);
????????? int sum=0;
????????? for(i=0;i ????????? {
????????????? //printf("i=%d? sum=%d\n",i,sum);
????????????? sum+=query(a[i],n-1,1);
???????????? // printf(">>>");
????????????? update(a[i],1);
????????? }
???????? // printf("%d\n",sum);
????????? int ans=99999999;
????????? if(ans>sum)? ans=sum;
?????????? for(i=0;i ?????????? {
?????????????? sum=sum-a[i]+n-1-a[i];
?????????????? if(ans>sum) ans=sum;
?????????? }
?????????????? printf("%d\n",ans);
??? }
??? return 0;
}
下面是归并排序方法：
套用归并排序模板
[cpp]
#include??
#include??
int ans,a[5050],b[5050];?
void merge(int left,int mid,int right)?
{?
??? int i,j,cnt=0;?
??? int *p;?
??? p=(int *)malloc((right-left+1)*sizeof(int));?
??? i=left;?
??? j=mid+1;?
??? while(i<=mid&&j<=right)//这时候i 和 j 指向的部分都排序完毕了 现在合并??
??? {?
??????? if(a[i]<=a[j])?
??????? {?
??????????? p[cnt++]=a[i];?
??????????? i++;?
??????? }?
??????? else?
??????? {?
??????????? p[cnt++]=a[j];?
??????????? j++;?
??????????? ans+=mid-i+1;//第i个比j大 由于i已经从小到大排过序了 那么i+1到mid的也会比j大??
??????? }?
??? }?
??? while(i<=mid)?
??? {?
??????? p[cnt++]=a[i++];?
??? }?
??? while(j<=right)?
??? {?
??????? p[cnt++]=a[j++];?
??? }?
??? cnt=0;?
??? for(i=left;i<=right;i++)?
??????? a[i]=p[cnt++];?
??? free(p);?
?
}?
void merge_sort(int left,int right)?
{?
??? if(left ??? {?
??????? int mid;?
??????? mid=(left+right)/2;?
??????? merge_sort(left,mid);?
??????? merge_sort(mid+1,right);?
??????? merge(left,mid,right);?
???