题意
????? 求一列数字的逆序数。
?
思路
????? 由于数字很大,所以不能直接求,这里先对原数列排序之后,求出原下标的逆序数即可
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define lowbit(x) (x&(-x)) using namespace std; const int nMax = 500010; typedef long long ll; struct rrr{ ll a,b; }num[nMax]; bool cmp(rrr a, rrr b){ if(a.a<b.a)return 1; return 0; } int n, arr[nMax]; void add(int loc, int val){ while(loc <= n){ arr[loc] += val; loc += lowbit(loc); } } int sum(int loc){ int res = 0; while(loc >= 1){ res += arr[loc]; loc -= lowbit(loc); } return res; } int main(){ int i; while(scanf("%d",&n)!=EOF&&n){ for(i = 1; i <= n; i ++){ scanf("%I64d",&num[i].a); num[i].b = i; } sort(num + 1, num + n + 1 ,cmp); memset(arr, 0,sizeof(arr)); ll res = 0; for(i = 1; i <= n; i++){ res += num[i].b - 1 - sum(num[i].b); // cout<<num[i].b<<" "<<sum(num[i].b)<<endl; add(num[i].b, 1); } printf("%I64d\n",res); } return 0; }
?
原文:http://bbezxcy.iteye.com/blog/2166082