2018暑假多校赛【第二场】【归并排序】【逆序数】-Swaps and Inversions-YZHHHHHHH

Swaps and Inversions

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1662    Accepted Submission(s): 615

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 --> 每交换一次相邻的两个数所需要支付的代价

输出所需最小代价

比如第二组数据：有3、2、1 长度为3的序列，初始逆序对为3，因为只有3组逆序对，且存在一对逆序对的代价为1 ，交换1次代价为666，明显3小于666，所以最后答案为3。

题解：

很容易得出每一次交换可以减少一对逆序对，所以我们设逆序对数为 cnt，交换次数为 k，设所需代价ans。

得出公式，ans = (cnt-k)*x + k*y。化简得 ans = (y-x)*k + cnt*x。我们得出两个未知数cnt 和 k。只要把cnt 逆序对数求出，k就求出了。

所以先要解决求逆序对问题。

有两种解法：1、离散化+树状数组     2、归并排序

这里我选择了用归并排序，有需要的自己看看，借用大佬的博客。

求出cnt 后，得出0 <= k <= cnt。所以此时ans就变成一个很简单的函数 (y = k*b+c)。

可以发现，两个都是单调函数，所以只要看x,y那个更大就行最终答案就是ans * min(x,y)。

代码

#include <stdio.h>
#define ll long long
ll c = 0;	//用来记逆序对数 
// 合并两个有序的数组 mergeArrary
void mergeArrary(ll a[], ll first, ll mid, ll last, ll temp[]){
    
    ll i = first, j = mid+1;
    ll n = mid, m = last;
    ll k = first;
    while (i <= n && j <= m){
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else {
            temp[k++] = a[j++];
			c += j-k;	//记录逆序对的核心，手算一遍就会明白其中的妙处 
        }
    }
    while (i <= n) temp[k++] = a[i++];
    while (j <= m) temp[k++] = a[j++];
    for (int i = first; i < k; i++){
        a[i] = temp[i];	//更新原数组 
    }
   
}
// 归并算法，递归 
void mergeSort(ll a[], ll first, ll last, ll temp[]){
    if (first < last){
        ll mid = (first+last) / 2;
        mergeSort(a, first, mid, temp);
        mergeSort(a, mid+1, last, temp);
        mergeArrary(a, first, mid, last, temp); 
    }
}

int main(){
    ll n,x,y;
    while (scanf("%lld %lld %lld",&n,&x,&y) != EOF){
        ll a[100005],t[100005];
        for (ll i = 0; i < n; i++){
            scanf("%lld",&a[i]);
        }
        c = 0;
        mergeSort(a, 0, n-1, t);
        if (x < y) 
			printf("%lld\n",c*x);
        else
            printf("%lld\n",c*y);
    }
}

还有就是要开long long 数据挺大的