【hdu 6318】Swaps and Inversions（归并排序模板）

ゝ一世哀愁。 2022-05-18 03:20 124阅读 0赞

Problem Description：

Long long ago, there was an integer sequence a.  
Tonyfang think this sequence is messy, so he will count the number of inversions in this sequence. Because he is angry, you will have to pay x yuan for every inversion in the sequence.  
You don't want to pay too much, so you can try to play some tricks before he sees this sequence. You can pay y yuan to swap any two adjacent elements.  
What is the minimum amount of money you need to spend?  
The definition of inversion in this problem is pair (i,j) which 1≤i<j≤n and ai>aj.

Input：

There are multiple test cases, please read till the end of input file.  
For each test, in the first line, three integers, n,x,y, n represents the length of the sequence.  
In the second line, n integers separated by spaces, representing the orginal sequence a.  
1≤n,x,y≤100000, numbers in the sequence are in \[−109,109\]. There're 10 test cases.

Output：

For every test case, a single integer representing minimum money to pay.

Sample Input：

3 233 666  
1 2 3  
3 1 666  
3 2 1

Sample Output：

0  
3

题意：多组测试，输入有n，x，y；n代表序列的长度，x代表每一次反转需要支付x元，y代表每交换相邻的数需要支付y元。问给这个原始序列排好序最少支付多少钱。

思路：看到这道题可能你们会想到冒泡或sort排序，但那样做肯定会超时，因此我们想到了归并排序，因为归并排序的速度仅次于快速排序，而且用归并排序的算法可以很简单的算出一个数列中的逆序对数。这道题它是想让我们比较反转花的钱和交换花的钱，然后输出较小的辣个，但如果用逆序对的话，它的反转次数和交换次数是一样的，所以我们只用比较x和y的大小就可以了，这就是我们用归并排序的好处。

（这里如果有大佬想回顾一下归并排序的的话，可以看看这个博客[https://blog.csdn.net/qq\_41181772/article/details/81267713][https_blog.csdn.net_qq_41181772_article_details_81267713]，是我这个菜鸟自己总结的归并排序，写的不好还望指教）

My DaiMa：

#include<iostream>
    #include<stdio.h>
    using namespace std;
    const int Max = 100005;
    typedef long long ll;
    ll sum,a[Max],t[Max];
    void merge_sort(int l,int r)
    {
        if(r == l)
            return ;//结束条件
        int m = (l + r) >> 1;//相当于m = (l + r) / 2;
        merge_sort(l, m);
        merge_sort(m + 1, r);//二分查找
        int i = l, j = m + 1, k = l;
        while(j <= r || i <= m)
        {
            if(j > r || (i <= m && a[i] <= a[j]))
                t[k++] = a[i++];
            else
                t[k++] = a[j++], sum += m - i + 1;
        }
        for(i = l; i <= r; i++)
            a[i] = t[i];
    }
    int main()
    {
        int n;
        ll x,y;
        while(~scanf("%d %lld %lld",&n,&x,&y))
        {
            sum = 0;
            for(int i = 1;i <= n;i ++)
                scanf("%lld",&a[i]);
            merge_sort(1,n);
            printf("%lld\n",sum*min(x,y));
        }
    }

最后附小僵尸一枚

![20160914135356_krSRX.jpeg][]

[https_blog.csdn.net_qq_41181772_article_details_81267713]: https://blog.csdn.net/qq_41181772/article/details/81267713
[20160914135356_krSRX.jpeg]: http://img5.duitang.com/uploads/item/201609/14/20160914135356_krSRX.jpeg