Ultra-QuickSort ————分治

妖狐艹你老母 2022-05-17 00:52 114阅读 0赞

n 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 .  
![这里写图片描述][b3530eaa8fa98ef394d3639722240a8c_v_1532766237]

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.  
**Sample Input**  
5  
9  
1  
0  
5  
4  
3  
1  
2  
3  
0  
**Sample Output**  
6  
0

--------------------

就是求逆序数对数

--------------------

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    using namespace std;
    typedef long long ll;
    vector<int> A;
    int n;
    ll merge_count(vector<int> &a)
    {
        int n=a.size();
        if(n<=1)    return 0;
    
        ll cnt=0;
        vector<int> b(a.begin(),a.begin()+n/2);
        vector<int> c(a.begin()+n/2,a.end());
        cnt += merge_count(b);
        cnt += merge_count(c);
    
        int ai=0,bi=0,ci=0;
        while(ai<n)
        {
            if(bi<b.size() && (ci == c.size() || b[bi] <= c[ci]))
                a[ai++] = b[bi++];
            else
            {
                cnt += n / 2 - bi;
                a[ai++] = c[ci++]; 
            }
        }
        return cnt;
    }
    int main()
    {
        while(~scanf("%d",&n)&&n)
        {
            int x;
            A.clear();
            for(int i=0;i<n;i++)
            {
                scanf("%d",&x);
                A.push_back(x);
            }
            printf("%lld\n",merge_count(A));
        }
        return 0;
    }

[b3530eaa8fa98ef394d3639722240a8c_v_1532766237]: https://odzkskevi.qnssl.com/b3530eaa8fa98ef394d3639722240a8c?v=1532766237