乾坤大挪移
给定一个n，代表有1~n个数，然后给定这n个数的一个序列，可以进行的操作是不断交换相邻的两个数字，使得最后的结果是一个上升序列。例如1 3 2，交换2和3，就能得到1 2 3,即为所求的序列，此时只交换了一步，所以输出1.
有多组输入，每组输入分两行，第一行是一个整数n，代表共n个数字（2<= n <= 1200），第二行为1~n这n个数字的一个随机排列。
对于每组数据，输出其所需要移动的步数。
3 1 3 2 4 1 2 3 4
1 0
解题：逆序数+数状数组
#include<cstdio> #include<cmath> #include<cstring> using namespace std; #define MAXN 2000 int c[MAXN]; int lowbit(int x) { return x&(-x); } void update(int x) { while(x<MAXN) { c[x]++; x+=lowbit(x); } } int sum(int x) { int s=0; while(x>0) { s+=c[x]; x-=lowbit(x); } return s; } int main() { int n; int i,s,a; while(scanf("%d",&n)==1) { s=0; memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { scanf("%d",&a); s+=(a-sum(a)-1); update(a); } printf("%d\n",s); } return 0; }