ITKeyword,专注技术干货聚合推荐

注册 | 登录

百练 求排列的逆序数

q547550831 分享于 2016-07-31

推荐:分治法求解逆序数

   在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。    

2020腾讯云“6.18”活动开始了!!!(巨大优惠重现!4核8G,5M带宽 1999元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1059

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

百练 求排列的逆序数


总时间限制: 内存限制:
1000ms 65536kB

描述

在Internet上的搜索引擎经常需要对信息进行比较,比如可以通过某个人对一些事物的排名来估计他(或她)对各种不同信息的兴趣,从而实现个性化的服务。

对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列 i1,i2,…,in ,如果其中存在j,k,满足 j < k 且 ij>ik , 那么就称 (ij,ik) 是这个排列的一个逆序。

一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1),因此该排列的逆序数就是8。显然,由1,2,…,n 构成的所有n!个排列中,最小的逆序数是0,对应的排列就是1,2,…,n;最大的逆序数是n(n-1)/2,对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。

现给定1,2,…,n的一个排列,求它的逆序数。

推荐:poj2299 逆序数 归并

Ultra-QuickSort Time Limit: 7000MS   Memory Limit: 65536K Total Submissions: 36311   Accepted: 13088 Description In this problem, you have to analyze

输入

第一行是一个整数n,表示该排列有n个数(n <= 100000)。

第二行是n个不同的正整数,之间以空格隔开,表示该排列。

输出

输出该排列的逆序数。

样例输入

6
2 6 3 4 5 1

样例输出

8

提示

  1. 利用二分归并排序算法(分治);

  2. 注意结果可能超过int的范围,需要用long long存储。

#include <cstdio>

using namespace std;

const int MAX_NUM = 100000 + 5;
long long seq[MAX_NUM];
int N;
long long ans;

void reSeq(long long* seq, int lef, int righ) {
    if(lef >= righ) {
        return ;
    }
    int mid = lef + (righ - lef) / 2;
    reSeq(seq, lef, mid);
    reSeq(seq, mid + 1, righ);

    int totalSize = righ - lef + 1;
    long long tmp[totalSize];
    int n = lef;
    int m = mid + 1;
    int i = 0;
    while(n <= mid || m <= righ) {
        if(m > righ || (n <= mid && seq[n] <= seq[m])) {
            tmp[i++] = seq[n++];
        } else {
            tmp[i++] = seq[m++];
            ans += mid - n + 1;
        }
    }
    i = lef;
    for(int j = 0; j < totalSize; j++) {
        seq[i++] = tmp[j];
    }
}

void reSeqNum(long long* seq, int n) {
    reSeq(seq, 0, n - 1);
}

int main() {
    scanf("%d", &N);
    for(int i = 0; i < N; i++) {
        scanf("%ld", &seq[i]);
    }
    ans = 0;
    reSeqNum(seq, N);
    printf("%ld\n", ans);
    return 0;
}

推荐:poj1084(求逆序数)

题意:给一个长度为n的序列,每次交换相邻的元素,求最少的交换次数。也就是求冒泡排序的交换次数。 解题思路: 对于冒泡排序,每一次相邻交换,那么这个序列的

百练 求排列的逆序数 总时间限制: 内存限制: 1000ms 65536kB 描述 在Internet上的搜索引擎经常需要对信息进行比较,比如可以通过某个人对一些事物的排名来估计他(或她)对各种不同信息的兴趣,

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。