题目链接：http://poj.org/problem?id=2299
| Time Limit: 7000MS | Memory Limit: 65536K | |
| Total Submissions: 75831 | Accepted: 28402 |
Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence Input
Output
Sample Input
5 9 1 0 5 4 3 1 2 3 0
Sample Output
6 0
Source
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> using namespace std; typedef long long LL; const LL mod=1e9+7; const LL INF=1e9+7; const int maxn=5e5+50; LL a[maxn],b[maxn],c[maxn]; LL len; LL lowbit(LL x) { return x&(-x); } LL query(LL x) { LL ret=0; while(x>0) { ret+=c[x]; x-=lowbit(x); } return ret; } void update(LL x) { while(x<=500000) { c[x]++; x+=lowbit(x); } } int main() { LL N; while(scanf("%lld",&N)!=EOF) { if(N==0) break; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); LL ans=0; for(int i=1;i<=N;i++) { scanf("%lld",&a[i]); b[i]=a[i]; } sort(b+1,b+N+1); len=unique(b+1,b+N+1)-b; for(int i=1;i<=N;i++) { // cout<<"*"<<endl; LL x=lower_bound(b+1,b+len+1,a[i])-b;//找到a[i]在b数组中所在位置 ans+=i-query(x-1)-1;//query找在x之前的数有多少个 这些都是顺序对的 update(x); } printf("%lld\n",ans); } return 0; }
原文：https://www.cnblogs.com/caijiaming/p/10896713.html