菜鸟题解 POJ-2299 Ultra-QuickSort

原题直达

https://vjudge.net/contest/582185#problem/G

题干

原题面
参考翻译

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 – the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

在这个问题中，你必须分析一个特定的排序算法。该算法通过交换两个相邻的序列元素来处理n个不同整数的序列，直到序列按升序排序。对于输入序列

9 1 0 5 4，

Ultra-QuickSort产生输出

0 1 4 5 9。

您的任务是确定为了对给定的输入序列排序，Ultra-QuickSort需要执行多少交换操作。

Input

输入包含几个测试用例。每个测试用例都以包含单个整数 n 的一行开始，n < 500,000——输入序列的长度。以下n行每一行包含一个整数0≤a[i]≤999,999,999，即第i个输入序列元素。输入以长度为n = 0的序列终止。这个序列不能被处理。

Output

对于每个输入序列，程序打印单行，其中包含整数op，这是对给定输入序列排序所需的最小交换操作数。

测试案例

Input

Output

1
2

6
0

题意与思路

Ultra-QuickSort 通过 交换两个相邻的元素 来实现从小到大的排序。

对于题目给出的案例，输入序列为 9 1 0 5 4，其交换过程如下：

交换行为发生在：

{9 和 1} {9 和 0} {9 和 5} {9 和 4} {1 和 0} {5 和 4}

可以看出，对于原序列中的任意两个元素，如果 它们的大小顺序与 “从小到大” 不符，那么它们之间一定会发生交换。

从而，本题可以转化为 求给定序列的逆序对数，采用分治的思想求解。

求逆序对数

采用分治法求逆序对数的基本思想是 在归并排序的过程中记录逆序对数：

分：将当前序列分为左右两部分

治：递归调用自身，完成左右两部分各自从小到大的排序，并得到各自的 逆序对数

合：考察左半部分和右半部分之间的逆序对数，由于本题要求从小到大排序，因此当 左半部分的元素大于右半部分的元素 时，产生逆序对数。

分

#define ll long long  // long long太长了，给它定义一个缩写

vector<ll> v;  // 用于存储序列

// left-当前序列开头元素在v中的下标 right-当前序列末尾元素在v中的下标
// 返回值-逆序对数
ll sort_and_count_inversions(int left, int right){
    int len = right - left + 1;
    if (len == 1)
        return 0;  // 当前序列长度为1的时候，不存在逆序对数，返回0

    int mid = left + (right - left) / 2;  // 按照中间元素（下标）拆分序列
    ll l_number = sort_and_count_inversions(left, mid);  // 左半部分的逆序对数
    ll r_number = sort_and_count_inversions(mid + 1, right);  // 右半部的逆序对数
    ll m_number = merge(left, mid, mid+1, right);  // 左、右之间的逆序对数

    return l_number + r_number + m_number;
    
}

合

当出现左序列的某一元素 $a_i$ 大于右序列的某一元素 $b_j$ 时，由于左右子序列都是升序的，因此有：

b_j < a_i < a_{i+1} <\cdots<a_{len_1}

也就是说，每当出现这样的逆序对 $(a_i,b_j)$ 时，同时意味着出现 $(len_1-i)$ 个逆序对 $(a_{i+1},b_j), \dots, (a_{len_1}, b_j)$ 。

// l1, r1 - 左序列的首元素下标和尾元素下标
// l2, r2 - 右序列的首元素下标和尾元素下标
// ps. 实际上 r2 = r1 + 1, 且 r1 = mid, 因此有效下标实际上只有 l1 和 r2
ll merge(int l1, int r1, int l2, int r2){
    ll cnt = 0;  // 记录合并过程中产生的逆序对数
    int h1 = 0, h2 = 0;  // 左、右序列用于遍历的下标
    int len1 = r1 - l1 + 1;  // 左序列的长度
    vector<ll> v_merge;  // 储存合并的序列
    
    for (int i = l1; i < r2; i++){
        if(v[l1 + h1] <= v[l2 + h2]){  // 正序
            v_merge.push_back(v[l1 + h1]);
            h1 ++;
            if(l1 + h1 > r1){  // 左子集已全部加入合并序列
                // 将右子集全部加入合并序列
                v_merge.push_back(v[l2 + h2]);
                h2 ++;
                while (l2 + h2 <= r2){
                    v_merge.push_back(v[l2 + h2]);
                    h2++;
                }
                break;
            }
        }
        else{  // 逆序, 需要记录逆序对数
            v_merge.push_back(v[l2 + h2]);
            h2 ++;
            cnt += len1 - h1;  // 记录逆序对数
            if(l2 + h2 > r2){  // 右子集已全部加入合并序列
                v_merge.push_back(v[l1 + h1]);
                h1 ++;
                while (l1 + h1 <= r1){
                    v_merge.push_back(v[l1 + h1]);
                    h1 ++;
                }
                break;
            }
        }
    }
    
    for(int i = l1;i <= r2;i++)  // 将排序好的序列覆盖到原序列
        v[i] = v_merge[i - l1];
    
    return cnt;
}

题解

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#define ll long long

using namespace std;

int n;
vector<ll> v;
ll c;

ll merge(int l1, int r1, int l2, int r2){
    ll cnt = 0;
    int h1 = 0, h2 = 0;
    int len1 = r1 - l1 + 1;
    vector<ll> v_merge;
    for (int i = l1; i < r2; i++){
        if(v[l1 + h1] <= v[l2 + h2]){  // 正序
            v_merge.push_back(v[l1 + h1]);
            h1 ++;
            if(l1 + h1 > r1){  // 左子集已全部加入
                v_merge.push_back(v[l2 + h2]);
                h2 ++;
                while (l2 + h2 <= r2){
                    v_merge.push_back(v[l2 + h2]);
                    h2++;
                }
                break;
            }
        }
        else{  // 逆序
            v_merge.push_back(v[l2 + h2]);
            h2 ++;
            cnt += len1 - h1;
            if(l2 + h2 > r2){  // 右子集已全部加入
                v_merge.push_back(v[l1 + h1]);
                h1 ++;
                while (l1 + h1 <= r1){
                    v_merge.push_back(v[l1 + h1]);
                    h1 ++;
                }
                break;
            }
        }
    }
    // cout<<", v = ";
    for(int i = l1;i <= r2;i++)
        v[i] = v_merge[i - l1];
    
    return cnt;
}

ll sort_and_count_inversions(int left, int right){
    int len = right - left + 1;
    if (len == 1){
        return 0;
    }

    int mid = left + (right - left) / 2;
    ll l_number = sort_and_count_inversions(left, mid);
    ll r_number = sort_and_count_inversions(mid + 1, right);
    ll m_number = merge(left, mid, mid+1, right);

    return l_number + r_number + m_number;
    
}


int main(){
    while (scanf("%d", &n) && n){
        v.clear();
        for (int i = 0; i < n; i++){
            scanf("%lld", &c);
            v.push_back(c);
        }
        printf("%lld\n", sort_and_count_inversions(0, v.size() - 1));
        
    }
    
    return 0;
}