逆序对数量利用归并排序
作者:
巷港
,
2022-04-08 17:33:42
,
所有人可见
,
阅读 150
利用归并排序求解
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int n;
int main()
{
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d",&a[i]);
int ans=0;
for (int i=0;i<n-1;i++)
{
for (int j=i+1;j<n;j++)
if (a[i]>a[j]) ans++;
}
cout<<ans<<endl;
return 0;
}
暴力9/11(狗头)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int n;
int main()
{
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d",&a[i]);
int ans=0;
for (int i=0;i<n-1;i++)
{
for (int j=i+1;j<n;j++)
if (a[i]>a[j]) ans++;
}
cout<<ans<<endl;
return 0;
}