AcWing 3715. 最少交换次数
原题链接
简单
作者:
飞舞
,
2021-06-23 15:21:04
,
所有人可见
,
阅读 423
前半题树状数组,后半题冒泡排序
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3+10;
int n;
int a[N],f[N];
int tr[N];
int p[N],s[N];
int lowbit(int x) // 返回末尾的1
{
return x & -x;
}
void add(int x,int v){
for(int i=x;i<=n;i+=lowbit(i)){
tr[i]+=v;
}
}
int query(int x){
int ans=0;
for(int i=x;i;i-=lowbit(i)){
ans+=tr[i];
}
return ans;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
int k=a[i];
f[a[i]]=i-query(k-1)-1;
add(k,1);
}
int ans=0;
for(int i=1;i<n;i++){
for(int j=1;j<n;j++){
if(a[j]>a[j+1]){
swap(a[j],a[j+1]);
ans++;
}
}
}
for(int i=1;i<=n;i++)
cout<<f[i]<<" ";
cout<<endl;
cout<<ans<<endl;
return 0;
}