TJU OJ 1218 Ultra-QuickSort问题描述输入输出解题思路C++代码

65 阅读 0 评论 43 点赞

我是靠谱客的博主外向小虾米，最近开发中收集的这篇文章主要介绍TJU OJ 1218 Ultra-QuickSort问题描述输入输出解题思路C++代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述

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.

输入

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.

输出

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.

6
0

解题思路

题目要求将一个序列转换为非递减序列，每次交换相邻的两个元素，求最小次数。
非递减序列可以定义为，一个序列中，任取一个数，后面不会出现比它大的数字。
那么想把一个序列变成非递减序列，我们可以首先将最大的数字移到后面，移动的步数是这个最大的数字后面的元素个数。同理，移动第二大的数字到倒数第二位…到这里已经不难看出，其实就是求这个序列的逆序数。
求一个序列的逆序数可以用归并排序，归并排序可以简单描述为左右两边都是一个有序数组(默认从小到大排序，为了方便描述，我把数组称作队列)，对左右两边的队头(队头是左右两边的最小元素)进行比较，谁更小就出队放在前面，继续比较队头元素。
融合左右两个队列时，当左边的队头元素比右边的队头元素大的时候，那么左边队列中剩下的其它元素也应该比右边所有元素大。那么逆序数就应该加上左边队列中的元素个数。
因此可以在分治实现归并的同时计算逆序数。

C++代码

#include <iostream>
#include <limits.h>
#define MAX INT_MAX
using namespace std;

int numArray[500005];
long long sum; // 用以记录逆序数 

void MergeSort(int left, int right){
    if(left == right){
        return;
    }
    int mid = (left + right) / 2;
    MergeSort(left, mid);
    MergeSort(mid + 1, right);

    int tempList[500005]; // 暂时用于存储归并排序结果的数组
    int leftNumber = mid - left + 1; // 左边剩余的数字
    int left_index = left, right_index = mid + 1;
    for(int i = left; i <= right; i++){
        if(right_index <= right && left_index <= mid) // 当左右两个游标没有越界的时候
        {
            if(numArray[left_index] > numArray[right_index]){ // 左边的首元素比右边的首元素大，逆序数需要加上左边元素剩余数量
                tempList[i] = numArray[right_index++];
                sum = sum + leftNumber;
            }
            else{
                tempList[i] = numArray[left_index++];
                leftNumber--;
            }
        }
        else if(left_index > mid){ // 左边越界
            tempList[i] = numArray[right_index++];
        }
        else{ // 右边越界
            tempList[i] = numArray[left_index++];
        }
    }
    for(int i = left; i <= right; i++){ // 把排序好的数组copy回去
        numArray[i] = tempList[i];
    }
}

int main(){
    int numCases;
    while(cin >> numCases && numCases){
        sum = 0;
        for(int i = 0; i < numCases; i++){
            cin >> numArray[i];
        }
        MergeSort(0, numCases - 1);
        cout << sum << endl;
    }
    return 0;
}