2018HDU多校联赛第二场

今天药忘吃喽~ 2022-05-19 14:00 196阅读 0赞

# 题目衔接：[http://acm.hdu.edu.cn/showproblem.php?pid=6318][http_acm.hdu.edu.cn_showproblem.php_pid_6318] #

# Swaps and Inversions #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 656    Accepted Submission(s): 259**

**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

**Source**

[2018 Multi-University Training Contest 2][]

题目大意：给你一堆无序的数，现在要你花费最少的代价将它变成有序的数，你可以用y元交换两个相邻数，或者用x元倒转两个数，这两个数必须是前者大于后者，且后者的下标大于前者下标

思路：比赛时不会，用了好多种办法，结束后学长说是用归并排序，弱弱表示没听过  
  
归并排序：什么是归并排序？

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路[归并][Link 1]。

例如设有数列\{6，202，100，301，38，8，1\}

初始状态：6,202,100,301,38,8,1

第一次归并后：\{6,202\},\{100,301\},\{8,38\},\{1\}，比较次数：3；

第二次归并后：\{6,100,202,301\}，\{1,8,38\}，比较次数：4；

第三次归并后：\{1,6,8,38,100,202,301\},比较次数：4；

总的比较次数为：3+4+4=11；

逆序数为14；

第一步中比较三次指的是第一次让6与202比，第二次100与301比第三次38与8比

第二步中比较四次分别是第一次100与6比，第二次100与202比，第三次是202与301比，第四次是1与8比

第三步中比较四次分别是第一次1与6比，第二次8与6比，第三次8与100比，第四次38与100比

所以一共11次

逆序数为14

什么是逆序数？如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个**逆序**。一个排列中逆序的总数就称为这个排列的**逆序数**。

例如4 3 2 1，43，41，42，32，31，21，均为逆序数，一共6对

所以本题代码：

#include<map>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<vector>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int N=1e5+10;
    typedef long long ll;
    int a[N],b[N];
    ll ans;
    void hebing(int l,int r)
    {
        if(l==r)
            return ;
        int mid=(l+r)>>1;
        hebing(l,mid);
        hebing(mid+1,r);
        int i=l,j=mid+1,k=l;
        while(i<=mid&&j<=r)
        {
            if(a[i]<=a[j])
            {
                b[k++]=a[i++];
            }
            else
            {
                b[k++]=a[j++];
                ans+=mid-i+1;
            }
        }
        while(i<=mid)
        {
            b[k++]=a[i++];
        }
        while(j<=r)
        {
            b[k++]=a[j++];
        }
        for(i=l; i<=r; i++)
            a[i]=b[i];
    }
    int main()
    {
        int n,x,y;
        while(scanf("%d%d%d",&n,&x,&y)!=EOF)
        {
            int i,j,k;
            memset(b,0,sizeof(b));
            for(i=1; i<=n; i++)
            {
                scanf("%d",&a[i]);
            }
            ans=0;
            hebing(1,n);
            printf("%lld\n",ans*min(x,y));
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_6318]: http://acm.hdu.edu.cn/showproblem.php?pid=6318
[2018 Multi-University Training Contest 2]: http://acm.hdu.edu.cn/search.php?field=problem&key=2018+Multi-University+Training+Contest+2&source=1&searchmode=source
[Link 1]: https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6/253741