排序 计蒜客

题目

分析

**思想：**将一组数从小到大排序，求其最小交换次数，一个单独数字的交换次数，应该就是求这个数前面有多少个数比此数要大的数的个数 ; 总的交换次数，就是求每个数的前面有多少个数比此数大的个数之和。

做到这里，应该想到之前所做的题目，棋子等级，这道题我没有写博文，就没办法贴出来，就是利用树状数组getsum()求一个数前面有多少个数比此数小。

但是题目是求比此数大的个数，而getsum()是求比此数小的个数，这就要好好思考一下了。

正好这道题目的取值范围很恶心，一个整数ai的取值范围是（ai<=10^9）,用正常的做法做的话，树状数组就必须开 10^9这么大，毫无疑问，一运行内存就爆炸，但是这里n的取值范围是（n<=500000），这样我们就可以使用离散化这个方法，将原本数据分别映射成1到500000的每个数，这样树状数组就只用开500010就可以了，然而我是将大的数映射成小的值，这样原本求比此数大的个数，就成了求比此数小的个数。

AC代码

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;

const int MAXN=500001;
int tree[MAXN];//树状数组用于存储离散化后的值，并求出每个值前面有多少个数比此值要大。
int num[MAXN];//原数组，录入数据
int temp[MAXN];//中间数组，存储离散化的结果
map<int,int> mp;//映射关系
int n,m;

bool cmp(int a,int b){
    return a>b;
}
void change(int x){
    for(;x<=m;x+=x&(-x)){
        tree[x]++;
    }
}
int getsum(int x){
    int res=0;
    for(;x;x-=x&(-x)){
        res+=tree[x];
    }
    return res;
}


int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++){//录入n个数据
        scanf("%d",&num[i]);
        temp[i]=num[i];
    }
    sort(temp,temp+n,cmp);//将n个数据从大到小排序
    m=unique(temp,temp+n)-temp;//去除相邻元素重复的值，将此值放入数组尾部，并统计出不重复的元素个数。
    for(int i=0;i<m;i++){//将原数组中的大值映射成小值，如把9->1；
        mp[temp[i]]=i+1;
    }
    int res=0;
    for(int i=0;i<n;i++){
        res+=getsum(mp[num[i]]-1);//统计比此数小的数有多少个，
        change(mp[num[i]]);//将此数插入树状数组
    }
    cout<<res<<endl;
    return 0;
}