逆序对 - 超快速排序

我不是女神ヾ 2022-03-20 05:58 146阅读 0赞

在这个问题中，您必须分析特定的排序算法----超快速排序。

该算法通过交换两个相邻的序列元素来处理n个不同整数的序列，直到序列按升序排序。

对于输入序列9 1 0 5 4，超快速排序生成输出0 1 4 5 9。

您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

**输入格式**  
输入包括一些测试用例。

每个测试用例的第一行输入整数n，代表该用例中输入序列的长度。

接下来n行每行输入一个整数ai,代表用例中输入序列的具体数据，第i行的数据代表序列中第i个数。

当输入用例中包含的输入序列长度为0时，输入终止，该序列无需处理。

**输出格式**  
对于每个需要处理的输入序列，输出一个整数op，代表对给定输入序列进行排序所需的最小交换操作数，每个整数占一行。

**数据范围  
0≤N<500000,  
0≤ai≤999999999**

**时/空限制： 7s / 64MB**

**输入样例：**  
5  
9  
1  
0  
5  
4  
3  
1  
2  
3  
0  
**输出样例：**  
6  
0

典型的纯求逆序对的题目。**求法：借用了归并排序的思路，在合并的时候，统计一下逆序对的个数。**  
**代码**

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    
    using namespace std;
    
    typedef long long ll;
    
    ll merge_sort(vector<ll> &num, int l, int r)
    {
        
    	if (l >= r) return 0;
    	ll res = 0;
    	int mid = l + r >> 1;
    	res += merge_sort(num, l, mid);
    	res += merge_sort(num, mid + 1, r);
    
    	static vector<ll> w;
    	w.clear();
    
    	int i = l, j = mid + 1;
    	while (i <= mid && j <= r){
        
    		if (num[i] < num[j]){
        
    			w.push_back(num[i++]);
    		}
    		else{
        
    			w.push_back(num[j++]);
    			res += mid + 1 - i;
    		}
    	}
    	while (i <= mid) w.push_back(num[i++]);
    	while (j <= r) w.push_back(num[j++]);
    
    	for (i = l, j = 0; j < w.size(); i++, j++)
    		num[i] = w[j];
    
    	return res;
    }
    
    int main()
    {
        
    	vector<ll> num;
    	int n;
    	while(cin >> n, n)
    	{
        
    	    num.clear();
    	    for(ll i = 0, a;i < n;i++)
    	    {
        
    	        cin >> a;
    	        num.push_back(a);
    	    }
    	    cout << merge_sort(num, 0, num.size() - 1) << endl;
    	}
    }