题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=1394
树状数组,一开始想搓了,没有想到:
当队头的数放到队尾时,队列中所有数的逆序数都有可能发生改变。。。
于是在扣除逆序数的时候,忘记减去新出现的逆序数!
#include<iostream> #include<cstdio> #include<cstring> #define ll (v<<1) #define rr (v<<1|1) #define max(a,b) ((a)>(b)?(a):(b)) using namespace std; int n; int s[5200]; int num[5200]; int rec[5200]; void add(int v){ while(v<=n){ num[v]++; v+=v&-v; } } int query(int v){ int sum=0; while(v>0){ sum+=num[v]; v-=v&-v; } return sum; } int main(){ int i,j,tmp,sum,mn; while(~scanf("%d",&n)){ memset(num,0,sizeof(num)); for(i=1;i<=n;i++){ scanf("%d",&s[i]); s[i]++; } sum=0; for(i=n;i>=1;i--){ // 建立BIT add(s[i]); rec[i]=query(s[i]-1); // 统计逆序数 sum+=rec[i]; //统计并记录逆序数 } memset(num,0,sizeof(num)); // 重建BIT mn=sum; for(i=1;i<=n;i++){ // 旧的和新的逆序数,都要减去 sum-=rec[i]+query(s[i]-1); add(s[i]); // 每次移到后面,即进入新的BIT sum+=n-s[i]; // 再加上新的逆序数 if(sum<mn) mn=sum; } printf("%d\n",mn); } return 0; }