POJ 1804 - Brainman - JOYK Joy of Geek, Geek News, Link all geek

POJ 1804 - Brainman

2 years ago

source link: https://exp-blog.com/algorithm/poj/poj1804-brainman/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

POJ 1804 - Brainman
Time: 1000MS
Memory: 30000K
难度: 初级
分类: 排序

和 [POJ2299](./>　可以参看 [POJ2299](./>　把 S[i] 和 s[i+1~n] 的元素逐个比较，如果 s[i] > s[k] (k∈[i+1,n]) 则逆序数 t++

解题方法一：归并排序

/*借助Mergesort求逆序数O(nlogn)*/

//Memory Time 
//228K   172MS 

#include<iostream>
using namespace std;

const int inf=1000001;
int t;  //数字序列s[]的逆序数

void compute_t(int* s,int top,int mid,int end)
{
    int len1=mid-top+1;
    int len2=end-mid;

    int* left=new int[len1+2];
    int* right=new int[len2+2];

    int i,j;
    for(i=1;i<=len1;i++)
        left[i]=s[top+i-1];
    left[len1+1]=inf;

    for(j=1;j<=len2;j++)
        right[j]=s[mid+j];
    right[len2+1]=inf;

    i=j=1;
    for(int k=top;k<=end;k++)
        if(left[i]<=right[j])
            s[k]=left[i++];
        else
        {
            s[k]=right[j++];
            t+=len1-i+1;
        }

    delete left;
    delete right;

    return;
}

void mergesort(int* s,int top,int end)
{
    if(top<end)
    {
        int mid=(top+end)/2;
        mergesort(s,top,mid);
        mergesort(s,mid+1,end);
        compute_t(s,top,mid,end);
    }
    return;
}
int main(void)
{
    int test;
    cin>>test;
    for(int p=1;p<=test;p++)
    {
        int n;  //数字序列s[]长度
        cin>>n;

        int* s=new int[n+1];

        for(int i=1;i<=n;i++)
            cin>>s[i];

        t=0;
        mergesort(s,1,n);

        cout<<"Scenario #"<<p<<':'<<endl<<t<<endl<<endl;

        delete s;
    }
    return 0;
}

解题方法二：直接求逆序数

/*直接求逆序数O(n^2)*/

//Memory Time 
//220K  188MS

#include <iostream>    
using namespace std;

int main(int i,int j)
{
    int test;
    cin>>test;
    for(int p=1;p<=test;p++)
    {
        int n;
        cin>>n;

        int* s=new int[n+1];
        for(i=1;i<=n;i++)
            cin>>s[i];

        int t=0;  //s[]的逆序数
        for(i=1;i<=n-1;i++)   //把S[i]和s[i+1~n]的元素逐个比较
            for(j=i+1;j<=n;j++)
                if(s[i]>s[j])  //如果s[i] > s[j] (j∈[i+1,n]) 
                    t++;   //则逆序数t++

        cout<<"Scenario #"<<p<<':'<<endl<<t<<endl<<endl;

        delete s;
    } 
    return 0;
}

Recommend