Swaps and Inversions (归并排序)

2018-08-02

Swaps and Inversions

题意

数逆序数对，再乘以min(x,y)即可。这里我发现逆序数对数有x个，就可以通过交换相邻数字x次使得它不存在逆序数。

用归并排序可以得到逆序数对个数。

看！代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
typedef long long ll;
long long sum;
int a[500005];
int temp[500005];
void sort2(int a[],int l,int mid,int r)
{
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j])
        {
            temp[k++]=a[i++];
        }
        else
        {
            temp[k++]=a[j++];
            sum+=mid-i+1;
        }
    }
    while(i<=mid)  temp[k++]=a[i++];
    while(j<=r)    temp[k++]=a[j++];

    for(int i=l,k=0; i<=r; k++,i++)
        a[i]=temp[k];
}

void sort1(int a[],int l,int r)
{
    int mid;
    if(l<r)
    {
        mid=(l+r)/2;
        sort1(a,l,mid);
        sort1(a,mid+1,r);
        sort2(a,l,mid,r);
    }
}
int main()
{
    int n;
    long long x,y;
    while(scanf("%d%lld%lld",&n,&x,&y)!=EOF)
    {
        sum=0;
        for(int i=0; i<n; i++)
            scanf("%d",&a[i]);
        sort1(a,0,n-1);
        printf("%lld\n",sum*min(x,y));
    }
    return 0;
}