废话不多说,直接上代码。
#include <cstdio>
#include <algorithm>
#define MAXN 1000
using namespace std;
struct node {
int val;
int index;
}nodes[MAXN];//输入数组
int n;//总数列长度
int a[MAXN];//离散化数组
int c[MAXN];//树状数组
int ans;//答案
int cmp(const node a,const node b) {
if(a.val<b.val)
return true;
else
return false;
}
int lowbit(int x) {
return x&(-x);
}
void update(int pos,int data) {
for(int i=pos;i<=n;i+=lowbit(i))
c[i] += data;
}
int sum(int x) {
int an = 0;
for(int i=x;i>=1;i-=lowbit(i))
an += c[i];
return an;
}
int main() {
scanf("%d",&n);
for(int temp,i=1;i<=n;i++) {
scanf("%d",&temp);
nodes[i].index = i;
nodes[i].val = temp;
}
sort(nodes+1,nodes+1+n,cmp);
for(int i=1;i<=n;i++) //离散化
a[nodes[i].index] = i;//在这里只关心数值的大小顺序而不是大小本身
for(int i=1;i<=n;i++) {
update(a[i],1);
ans += i - sum(a[i]);//之前比a[i]大的数
}
printf("%d",ans);
return 0;
}
顺便用离散化优化了一下。
这里的i一定要从1开始,如果为0的话lowbit()就无法使用了。