C1-H

题目要求

对覆盖[1, n]的序列a1, a2, … , an，只通过与相邻元素交换的操作，使序列有序。求最小操作次数。

核心算法与思路

• 简单想法：典型的冒泡排序思想。但是太慢

• 进阶想法：通过相邻交换操作消除包含一个元素之前的逆序对所需要的次数 = 包含该元素逆序对的数量 = 在该元素之前所有大于它的元素的数量，即同 C1-E方法求顺序对数，总序对数 - 顺序对数 = 逆序对数（对应到每个元素a[i]，则为i - sum(arr[i], ft)

• 细节：本题不需要将数据离散化（因为输入序列已经是离散化过的了）

代码

#include <bits/stdc++.h>
#define lowbit(x) x&-x
using namespace std;

int arr[100002];
int pos[100002];    //position of input sequence
void add(int index, int delta, int n, int* ft){
    for(; index <= n; index += lowbit(index)){
        ft[index] += delta;
    }
}

int sum(int index, int* ft){
    int ans = 0;
    for(; index > 0; index -= lowbit(index)){
        ans += ft[index];
    }
    return ans;
}

int main(){
    int group;
    int n;
    long long ans;
    cin >> group;
    while (group--){
        ans = 0;
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> arr[i];
        }

        int* ft = new int[n + 1];
        memset(ft + 1, 0, sizeof(int) * n);

        for(int i = 1; i <= n; i++){
            add(arr[i], 1, n, ft);
            ans += i - (sum(arr[i], ft));
        }
        cout << ans << endl;
    }
    return 0;
}