【POJ2188】Cow Laundry (归并排序,逆序数)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 21 日

依旧是利用归并模板。。。这里解释下题意:
牛们手短,每次只能移动上边或者下边相邻的一根线。
输入的数据是第一行是1号挂钩上下分别链接的线的编号,
第二行是二号钩上下分别链接的线的编号。
……
最后你需要你把错乱的线理顺就行了。。。

#include<stdio.h>  
#include<stdlib.h>  
using namespace std;  
//归并排序模板  
typedef int ElementType;  
int ans;  
void Merge(ElementType A[], ElementType TmpArray[], int Lpos, int Rpos, int RightEnd)  
{  
    int i , LeftEnd, NumElements, TmpPos;  
    LeftEnd = Rpos - 1;  
    TmpPos = Lpos;  
    NumElements = RightEnd - Lpos + 1;  
    while(Lpos <= LeftEnd && Rpos <= RightEnd)  
    {  
        if(A[Lpos] <= A[Rpos])  
            TmpArray[TmpPos++] = A[Lpos++];  
        else  
        {  
            ans += (LeftEnd - Lpos + 1);   
            TmpArray[TmpPos++] = A[Rpos++];  
        }  
    }  
    while(Lpos <= LeftEnd)   
    {  
        TmpArray[TmpPos++] = A[Lpos++];  
    }  
    while(Rpos <= RightEnd)  
    {  
        TmpArray[TmpPos++] = A[Rpos++];  
    }  
    for(i = 0; i < NumElements; ++i, --RightEnd)  
        A[RightEnd] = TmpArray[RightEnd];  
}  
void MSort(ElementType A[], ElementType TmpArray[], int Left, int Right)  
{  
    int Center = 0;  
    if(Left < Right)  
    {  
        Center = (Left + Right) >> 1;  
        MSort(A, TmpArray, Left, Center);  
        MSort(A, TmpArray, Center + 1, Right);  
        Merge(A, TmpArray, Left, Center + 1, Right);  
    }  
}  
void MergeSort(ElementType A[], int N)  
{  
    ElementType* TmpArray = NULL;  
    TmpArray = (ElementType*) malloc(N * sizeof(ElementType));  
    if(NULL != TmpArray)  
    {  
        MSort(A, TmpArray, 0, N - 1);  
        free(TmpArray);  
    }  
    else  
        printf("allocate temp memory fail\n");  
}  
int Arr[1001];  
int mires[2][1001];  
int main(int argc, char* argv[]){  
    freopen("1.txt","r",stdin);  
    int n;  
    while(scanf("%d",&n)!=EOF){  
        for(int i = 1; i <= n; ++i)  
            scanf("%d %d", &mires[0][i], &mires[1][i]);  
        for(int i = 1; i <= n; ++i) {  
            for(int j = 1; j <= n; ++j) {  
                if(mires[0][i] == mires[1][j]) {  
                    Arr[i-1] = j;  
                    break;  
                }  
            }  
        }  
        ans = 0;  
        MergeSort(Arr,n);  
        printf("%d\n",ans);  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日