归并排序求逆序数

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <ctime>
#include <map>
#include <set>
#define eps 1e-12
///#define M 1000100
///#define LL __int64
#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)?0:x)

using namespace std;

const int maxn = 30100;

LL a[maxn];
LL temp[maxn];
LL sum;

struct node
{
    LL y1;
    LL y2;
    int id;
}f[maxn];

void Merge(LL a[], int l, int mid, int r)
{
    int begin1 = l;
    int end1 = mid;
    int begin2 = mid+1;
    int end2 = r;
    int k = 0;
    while(begin1 <= end1 && begin2 <= end2)
    {
        if(a[begin1] < a[begin2])
        {
            temp[k++] = a[begin1];
            begin1++;
            sum += begin2-(mid+1);
        }
        else
        {
            temp[k++] = a[begin2];
            begin2++;
        }
    }
    while(begin1 <= end1)
    {
        temp[k++] = a[begin1];
        begin1++;
        sum += end2-mid;
    }
    while(begin2 <= end2)
    {
        temp[k++] = a[begin2];
        begin2++;
    }
    for(int i = l; i <= r; i++) a[i] = temp[i-l];
}

void MergeSort(LL a[], int l, int r)
{
    int mid = (l+r)>>1;
    if(l < r)
    {
        MergeSort(a, l, mid);
        MergeSort(a, mid+1, r);
        Merge(a, l, mid, r);
    }
}

时间: 10-29

归并排序求逆序数的相关文章

poj 2299 Ultra-QuickSort 归并排序求逆序数对

题目链接: http://poj.org/problem?id=2299 题目描述: 给一个有n(n<=500000)个数的杂乱序列,问:如果用冒泡排序,把这n个数排成升序,需要交换几次? 解题思路: 根据冒泡排序的特点,我们可知,本题只需要统计每一个数的逆序数(如果有i<j,存在a[i] > a[j],则称a[i]与 a[j]为逆序数对),输出所有的数的逆序数的和用普通排序一定会超时,但是比较快的排序,像快排又无法统计 交换次数,这里就很好地体现了归并排序的优点.典型的利用归并排序求逆

poj2299解题报告(归并排序求逆序数)

POJ 2299,题目链接http://poj.org/problem?id=2299 题意: 给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列. 思路: 其实就是求逆序数,那么直接向到的就是冒泡了,交换一次,记录一次即可.但是n的范围达到50W,冒泡O(n^2)的复杂度铁定超时. 然后...发现曾经微软有一道笔试题类似就是求逆序数的,对,没错,用归并. 例:合并两个序列(1,3,5)(2,4,6),新序列第二个元素是2,那么它和它前面的3.5形成了逆序数对

POJ 2299 Ultra-QuickSort (求逆序数:离散化+树状数组或者归并排序求逆序数)

Ultra-QuickSort Time Limit: 7000MS   Memory Limit: 65536K Total Submissions: 55048   Accepted: 20256 Description In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swappin

归并排序 求逆序数 链表的归并排序 多线程归并排序 java

import java.util.Scanner; public class Main { private static int count=0; public static void mergesort(int a[],int low,int high) { if(low<high) { int mid=(low+high)>>1; mergesort(a,low,mid); mergesort(a,mid+1,high); merge(a,low,mid,high); } } pri

E - 归并排序 求逆序数

Description One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC'', this measure is 5, since D is greater than four letters to

4thweek contest.A 归并排序求逆序数

题目: bobo has a sequence a 1,a 2,…,a n. He is allowed to swap two adjacent numbers for no more than k times. Find the minimum number of inversions after his swaps. Note: The number of inversions is the number of pair (i,j) where 1≤i<j≤n and a i>a j.

归并排序求逆序数对。

1 #include <iostream> 2 #include <stdio.h> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6 int high[100010]; 7 int temp[100010]; 8 int angry[100010]; 9 int num; 10 void mergesort(int first,int mid,int last) 11 { 1

归并排序_逆序数

归并排序求逆序数 在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序.一个排列中逆序的总数就称为这个排列的逆序数.一个排列中所有逆序总数叫做这个排列的逆序数.也就是说,对于n个不同的元素,先规定各元素之间有一个标准次序(例如n个 不同的自然数,可规定从小到大为标准次序),于是在这n个元素的任一排列中,当某两个元素的先后次序与标准次序不同时,就说有1个逆序.一个排列中所有逆序总数叫做这个排列的逆序数. 1 #include<cstdio> 2 #in

求逆序数(归并排序)

求逆序数 时间限制:2000 ms  |  内存限制:65535 KB 难度:5 描述 在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序.一个排列中逆序的总数就称为这个排列的逆序数. 现在,给你一个N个元素的序列,请你判断出它的逆序数是多少. 比如 1 3 2 的逆序数就是1. 输入 第一行输入一个整数T表示测试数据的组数(1<=T<=5) 每组测试数据的每一行是一个整数N表示数列中共有N个元素(2〈=N〈=1000000) 随后的一行共有N个整