【详解】Sort it HDU - 2689(冒泡排序交换次数经典问题) ⭐⭐⭐

57 阅读 0 评论 38 点赞

我是靠谱客的博主自信水池，最近开发中收集的这篇文章主要介绍【详解】Sort it HDU - 2689(冒泡排序交换次数经典问题) ⭐⭐⭐，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Sort it HDU - 2689

You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need.
For example, 1 2 3 5 4, we only need one operation : swap 5 and 4.

Input

The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n.

Output

For each case, output the minimum times need to sort it in ascending order on a single line.

Examples

Sample Input
3
1 2 3
4
4 3 2 1
Sample Output
0
6

Hint

题意:

给出一个序列, 求出该序列冒泡排序的交换次数. 即该序列中逆序数的对数

题解:

让我来试着详细阐述一下这个经典问题: 冒泡排序中交换的次数
最直观的解法当然就是直接在冒泡排序中加一个模拟判断, 复杂度N^2
但我们今天讨论的主要是NlogN的解法, 即使用树状数组
首先我们要考虑一下对sum和add的改变
sum(a[j])表示a[j] (i<j)的非逆序对数量, 那么j - sum(a[j]), add(a[j], 1)自然就是逆序对的数量, 表示a[j]出现的次数+1会产生的影响
还有几点需要注意.

要知道我们应该关心什么, 我们求逆序对的数量, 只关心数据间的相对大小即可, 而BIT又恰好要求范围要在[1,N]以内, 所以对于数据量过大的数据, 我们要进行离散化处理.
从0开始, add在后, 从1开始, add在前
只能变操作边求和, 不能一下操作完在求和, 因为可能会混淆因变量和自变量.

经验小结:

要时刻思考, 你要关心的到底是什么

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1<<30;
const LL maxn = 1e5+10;

LL N, C[maxn], a[maxn];
LL lowbit(LL x){return x&(-x);}
LL sum(LL x){
    LL res = 0;
    for(LL i = x; i > 0; i-=lowbit(i)) // lowbit(i);
        res += C[i];
    return res;
}
void add(LL x, LL v){
    for(LL i = x; i <= N; i+=lowbit(i))
        C[i] += v;
}
int main()
{
    while(cin >> N){
        ms(a, 0); ms(C, 0);
        for(int i = 1; i <= N; i++)
            cin >> a[i];
        LL ans = 0;
        for(int j = 1; j <= N; j++){
            add(a[j], 1);
            ans += j-sum(a[j]);
        }
        cout << ans << endl;
    }
	return 0;
}