poj1007DNASorting

发表于: 2013年01月18 00:00

一道求逆序数的题.逆序数的含义是在一个排列中,如果一对数的前后位置与大小顺序相反, 即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数

逆序数的求法之一就是暴力直接计数,时间复杂度为O(n*n),第二种方法是通过改进归并排序求逆序数 复杂度为O(n*logn)

poj1804和这题类似,求最少的交换次数,应为每交换一次都能使逆序数减一.当逆序数为0时. 则这个序列就是有序的了.代码只有一点变化.就不再贴了

下面是poj1007的题,安逆序数大小稳定排序后输出

:::c++
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAX 100
using namespace std;
typedef struct pp
{
    int dd;
    char ss[MAX];
}SS;
SS pp[MAX];
char tt[MAX];
int cmp(SS a,SS b)
{
    if(a.dd==b.dd) return 0;
    else return a.dd<b.dd;
}
int sum;
void  merge(char *ss,int f,int m,int l)
{
    int i=f,j=m+1;
    int c=0;
    while(i<=m && j<=l)
    {
        if(ss[i]<=ss[j])
            tt[c++]=ss[i++];
        else
        {
            tt[c++]=ss[j++];
            sum+=(m-i+1);
        }
    }
    while(i<=m)
        tt[c++]=ss[i++];
    while(j<=l)
        tt[c++]=ss[j++];
    for(int k=0;k<c;k++)
        ss[f++]=tt[k];
}
void mergesort(char *ss,int f,int l)
{
    if(f==l) return ;
    int m=f+(l-f)/2;
    mergesort(ss,f,m);
    mergesort(ss,m+1,l);
    merge(ss,f,m,l);
}
int main()
{
    int n,m,i;
    char tt[MAX];
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++)
        scanf("%s",pp[i].ss);
    for(i=0;i<m;i++)
    {
        sum=0;
        strcpy(tt,pp[i].ss);
        mergesort(tt,0,n-1);
        pp[i].dd=sum;
    }
    sort(pp,pp+m,cmp);
    for(i=0;i<m;i++)
    {
        printf("%s\n",pp[i].ss);
    }
    return 0;
}
© 2018 - fluyy - 粤ICP备17114935号