poj1833---字典序算法

浏览数：25 / 时间：2015年06月08日

题意：给定一个序列，求它的下k个排列

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a,const void *b)
{
    return (*(int *)a-*(int *)b);
}

void getNext(int *arr,int n)
{
    int i,j,flag,t;
    for(i=n-2;i>=0;i--)
    {
        if(arr[i]<arr[i+1])
            break;
    }//找到左边小于右边，并返回左边数的下标
    if(i==-1)
    {
        qsort(arr,n,sizeof(arr[0]),cmp);
        return ;
    }//以防遇到递减数列，找不到
    flag=i+1;
    for(j=i+2;j<n;j++)//当i==n-2,不走这个循环，那么倒数第二个数后面就只有一个数比他大，可能就要直接交换保证最小增长
    {
        if(arr[j]>arr[i])//假设说倒数第二个数大于倒数第三个数，可是倒数第一个数比倒数第三个数小
            flag=j;//flag始终记录当前比a[i]大的值的下标
    }
    t=arr[flag];
    arr[flag]=arr[i];
    arr[i]=t;
    qsort(&arr[i+1],n-1-i,sizeof(arr[0]),cmp);//有可能要qsort一个数
}

int main()
{
    int a[1025],ncase,i;
    scanf("%d",&ncase);
    while(ncase--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(i=0;i<k;i++){
        getNext(a,n);
        }
        for(i=0;i<n;i++)
        {
            printf("%d ",a[i]);
        }
        printf("\n");
    }
    return 0;
}

for(j=i+2;j<n;j++)//当i==n-2,不走这个循环，那么倒数第二个数后面就只有一个数比他大，可能就要直接交换保证最小增长
    {
        if(arr[j]>arr[i])//假设说倒数第二个数大于倒数第三个数，可是倒数第一个数比倒数第三个数小
            flag=j;//flag始终记录当前比a[i]大的值的下标
    }

这段代码有3涉及到最后两个，三个，四个的情况

字典序算法描述：从右边开始，遍历整个数列，先取数列的倒数第二个数与倒数第一个数相比，如果左边大于右边则让i--,让倒数第三个与倒数第二个相比，如果倒数第三个小于倒数第二个

那么此时循环结束，记下倒数第三个数的下标

否则直到找到左边一个数大于右边一个数为止，不过可能这个数列一开始就一个递减数列，i==0也不行，i==-1，循环被遍历完

此时在getNext里面直接qsort这个数列

分为四种情况：

1.倒数第2个<倒数第1个

2.倒数第3个<倒数第2个 a. 倒数第3个>倒数第1个 b. 倒数第3<倒数第1个

3.倒数第四个....反正从倒数第2个开始就有可能小于倒数第四个

flag的作用啊！！

字典序算法核心：为保证最小增长，将a[i]后面大于a[i]的最小的数与a[i]对调，然后从小到大排序，因为越小的数在越前面，数列越小

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。