有 n 个数 a1,a2,…,an,对于其中的两个数字x,y,如果满足 x 出现的位置在 y 出现的位置前面 并且 x 比 y 大,则称 (x,y) 为数组 a 的一个逆 序对。请问数组 a 的逆序对一共有多少个。形式的说,请求出有多少组 (i,j) 满足 i<j 并ai>aj。
第一行一个整数n。
接下来一行n个整数,a1,a2,…,an。
一个数,表示答案。
4 4 2 3 1
5
5 个逆序对分别为 (4,2),(4,3),(4,1),(2,1),(3,1)。
对于 100% 的数据,保证 2≤n≤100000,1≤ai≤n 并且每个数字都只会出现一次。
我的代码
#include <bits/stdc++.h>
using namespace std;
long long n,i,j,sum;
int main()
{
cin>>n;
long long a[n];
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
if(a[j]>a[i] && j<i)
{
sum++;
}
}
}
cout<<sum;
}
为啥会的0分??