算法1

(暴力枚举) 会有2个数据过不了

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

typedef long long LL;

const int N = 1e5 + 5;
int a[N];

int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++) cin >> a[i];

LL res = 0;
for (int i = 0; i < n; i ++)
{
    int j = i;
    while (j < n)
    {
        if (a[i] > a[j]) res ++;
        j ++;
    }
}
cout << res << endl;
return 0;

}

算法2

归并解法

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
int a[N], tmp[N], n;
LL res;

void merge_sort(int l, int r)
{
if (l >= r) return;

int mid = l + r >> 1;
merge_sort(l, mid), merge_sort(mid + 1, r);

int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
{
    if (a[i] > a[j])
    {
        tmp[k ++] = a[j ++];
        res += mid - i + 1;
    }
    else
    {
        tmp[k ++] = a[i ++];
    }
}

while (i <= mid) tmp[k ++] = a[i ++];
while (j <= r) tmp[k ++] = a[j ++];

for (int i = l, j = 0; i <= r; i ++, j ++) a[i] = tmp[j];

}

int main()
{
cin >> n;
for (int i = 0; i < n; i ++) cin >> a[i];

merge_sort(0, n - 1);

cout << res << endl;

return 0;

}