题目训练网址(密码hpuacm):https://vjudge.net/contest/243680
先说一下归并排序求逆序数法
什么事逆序数 戳这里
C题模板(归并排序求逆序数)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
vector<int> v;
LL merge_sort( vector<int> &v )
{
int n = v.size();
if( n <= 1 )
return 0;
LL cnt = 0;
vector<int> vb(v.begin(), v.begin() + n/2);
vector<int> ve(v.begin() + n/2, v.end());
cnt += merge_sort(vb);
cnt += merge_sort(ve);
int ai, bi, ci;
ai = bi = ci = 0;
while( ai < n )
{
if( bi < vb.size() && (ci == ve.size() || vb[bi] <= ve[ci]) )
v[ai++] = vb[bi++];
else
{
v[ai++] = ve[ci++];
cnt += n/2 - bi;
}
}
return cnt;
}
int main()
{
int n;
while( cin >> n )
{
int num;
v.clear();
for( int i=0; i<n; i++ )
{
scanf("%d", &num );
v.push_back(num);
}
printf("%d\n", merge_sort(v) );
}
return 0;
}