题意
给出一列n个数字,每一个数字都和其他数字不同,现在每次都把第一个数挪到最后面,求这个过程中这个数列逆序数对最少有多少对。
思路
先用线段树求出初始的数列逆序对数,再用第一个数列推出第二个,第三个直到第n个,输出最小的那个
这里关键是线段树在lonn的时间复杂度内求出当前数列逆序数对的方法,每次插入一个数,num[i] ,都查询一遍在num[i]+1---n中存在多少个已经插入的点。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int nMax = 6000; struct{ int l,r,val; }node[nMax*4]; int num[nMax]; void build(int l, int r, int u){ //建树 node[u].val = 0; node[u].l=l; node[u].r=r; if(l == r){ return; } int m = (l+r)/2; build(l , m ,u*2); build(m+1 , r, u*2 + 1); } void update(int p,int u){ //更新 int l = node[u].l; int r = node[u].r; if(l == r){ num[u]++; }else{ int m = (l + r)>>1 ; if( p <= m ){ update(p , u*2) ; }else{ update (p ,u * 2 + 1) ; } num[u] = ( num[u*2] + num[u*2+1]) ; } } int query(int le ,int ri ,int u){ //查询 int l = node[u].l; int r = node[u].r; if(le <= l && r <= ri ){ return num[u]; } int m = ( l + r ) >> 1 , res = 0 ; if(ri >= m + 1 ){ res += query(le , ri ,u * 2 + 1 ); } if( le <= m ){ res += query(le , ri , u * 2 ); } return res; } int ipt[nMax]; int main(){ int n , i, j ,a ,b ,c , sum ; while(scanf("%d",&n)!=EOF){ sum = 0; memset(num , 0, sizeof(num)); build(0 , n-1, 1); for(i = 0; i < n ; i++){ scanf("%d",&ipt[i]); update( ipt[i] ,1); sum += query(ipt[i] + 1 , n-1 , 1); } int ans = sum ; // cout<<ans<<endl; for(i = 0 ;i < n ; i++ ){ sum = sum - 2 * ipt[i] + n -1 ; ans = min(ans , sum); } printf("%d\n",ans); } return 0; }
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int nMax = 6000; struct{ int l,r,val; }node[nMax*4]; int num[nMax]; void build(int l, int r, int u){ //建树 node[u].val = 0; node[u].l=l; node[u].r=r; if(l == r){ return; } int m = (l+r)/2; build(l , m ,u*2); build(m+1 , r, u*2 + 1); } void update(int p,int u){ //更新 int l = node[u].l; int r = node[u].r; if(l == r){ num[u]++; }else{ int m = (l + r)>>1 ; if( p <= m ){ update(p , u*2) ; }else{ update (p ,u * 2 + 1) ; } num[u] = ( num[u*2] + num[u*2+1]) ; } } int query(int left, int right, int u){ // 查询。 if(node[u].l == left && node[u].r == right) return num[u]; if(right <= node[2*u].r) return query(left, right, 2*u); if(left >= node[2*u+1].l) return query(left, right, 2*u+1); int a = query(left, (node[u].l+node[u].r)/2, 2*u); int b = query((node[u].l+node[u].r)/2+1, right, 2*u+1); return a + b; } int ipt[nMax]; int main(){ int n , i, j ,a ,b ,c , sum ; while(scanf("%d",&n)!=EOF){ sum = 0; memset(num , 0, sizeof(num)); build(0 , n-1, 1); for(i = 0; i < n ; i++){ scanf("%d",&ipt[i]); sum += query(ipt[i], n-1 , 1); update( ipt[i] ,1); } int ans = sum ; // cout<<ans<<endl; for(i = 0 ;i < n ; i++ ){ sum = sum - 2 * ipt[i] + n -1 ; ans = min(ans , sum); } printf("%d\n",ans); } return 0; }
相关推荐
HDOJ题目分类HDOJ题目分类HDOJ题目分类
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
ACM ICPC HDOJ1000
hdoj解题代码,题目为1000-1050
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
codj,hdoj的源码(50-60题)
hdoj 2013 多校训练3标程+解题报告
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj1005 Number Sequence, 杭州电子科技大学oj题目代码
杭电OJ(1000-1099) AC 代码
HDOJ使用指南——公开版.docHDOJ使用指南——公开版.docHDOJ使用指南——公开版.doc