hdu 6318 Swaps and Inversions（归并排序）

Swaps and Inversions

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

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

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6318

题意：这道题的意思是说给你一个数组，你可以花x元或者y元去交换这个数组中相邻的两个数，问变为升序的时候最少花费多少元。

当时听（队友讲的）这个题的时候，脑子里第一反应是冒泡（没用过归并），肯定超时。最后我们也没有解决这个题。

作为菜鸟（手动笑哭）我还是先说一下归并排序吧！

把一个数组分成两半，先把前一半排序，再把后一半排序，把两半归并到一个新的数组中，然后在拷贝回原来的数组中。

归并排序测试：http://tk.hustoj.com/problem.php?id=1780

AC代码：

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
int a[100001],b[100001];
void Merge(int s,int m,int e)
{
    int p=0;
    int p1=s,p2=m+1;//一个指向第一个数组中的第一个数，一个指向第二个数组中的第一个数
    while(p1<=m&&p2<=e)
    {
        if(a[p1]<a[p2])//谁小谁在前
            b[p++]=a[p1++];
        else
            b[p++]=a[p2++];
    }
    while(p1<=m)
        b[p++]=a[p1++];
    while(p2<=e)
        b[p++]=a[p2++];
    for(int i=0;i<e-s+1;i++)
        a[s+i]=b[i];
}
void Merge_sort(int s,int e)
{
    if(s<e)
    {
        int m=s+(e-s)/2;
        Merge_sort(s,m);//前一半排序
        Merge_sort(m+1,e);//后一半排序
        Merge(s,m,e);//归并
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    Merge_sort(0,n-1);//0->(n-1)排序
    for(int i=0;i<n-1;i++)
        printf("%d ",a[i]);
    printf("%d\n",a[n-1]);
    return 0;
}
 

下面就来看这道题：会了归并排序以后这道题就简单很多了。下面就说怎么计算交换的次数。

s<=p1<=m,m+1<=p2<=e;

可以看图，在归并时，当a[p2]需要添加在数组中的时候，它必须要和1后面所有的数字交换，次数是：m-s+1;

下面看AC代码：

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
int a[100001],b[100001];
long long times;
void Merge(int s,int m,int e)
{
    int p=0;
    int p1=s,p2=m+1;
    while(p1<=m&&p2<=e)
    {
        if(a[p1]<=a[p2])//因为需要最小次数，所以这里是<=
            b[p++]=a[p1++];

        else
        {
            b[p++]=a[p2++];
            times+=m-p1+1;
        }
    }
    while(p1<=m)
        b[p++]=a[p1++];
    while(p2<=e)
        b[p++]=a[p2++];
    for(int i=0;i<e-s+1;i++)
        a[s+i]=b[i];
}
void Merge_sort(int s,int e)
{
    if(s<e)
    {
        int m=s+(e-s)/2;
        Merge_sort(s,m);
        Merge_sort(m+1,e);
        Merge(s,m,e);
    }
}
int main()
{
    int n,x,y;
    while(~scanf("%d%d%d",&n,&x,&y))
    {
        for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
        times=0;
        Merge_sort(0,n-1);
        printf("%lld\n",times*min(x,y));//注意数据范围
    }
    return 0;
}

刚开始因为while(~scanf("%d%d%d",&n,&x,&y))没有以EOF结束，T了n遍，后来不知道怎么就看出来了，然后就是<=那个地方和数据范围那里。一下午就做了两个题，一个是第一场贪心那个题，WA了n次，决定学了数据结构之后再去做，另外一个就是这个，在超时，超内存n次之后终于AC了。还是做得题太少了，就算当时会了归并，我觉得我有可能还是做不出来。找不到题的坑点（流泪）。