Blog·Tanky WooABOUTRSS

百练Grid POJ 1833 排列

09 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目地址:

http://poj.grids.cn/problem/1833/

此题有两种方法:

方法一:利用STL里的next_permutation()函数,当然,这样题就水了。

方法二:模拟,找出数列变化的特点。排列过程待补。。。大家记得提醒我。

直接发代码了。

方法一:(STL)

// Grid 1833
// Author: Tanky Woo
#include 
#include 

using namespace std;

#define MAX 1034
int ans[MAX];
// www.wutianqi.com
int main()
{
    int nCases;
    int num, k, i, j;
    scanf("%d", &nCases;);
    while(nCases--)
    {
        scanf("%d %d", #, &k;);
        for(i = 1; i <= num; ++i)
            scanf("%d", &ans;[i]);
        for(i = 0; i < k; ++i)
            next_permutation(ans+1, ans+num+1);

        for(j = 1; j <= num; ++j)
            printf("%d ", ans[j]);
        printf("\n");
    }
    return 0;
}

方法二:(模拟)

// Grid 1833
// Author: Tanky Woo
#include 
using namespace std;

#define MAX 1034
int ans[MAX];

int MyCompare(const void *e1, const void *e2)
{
    return *((int*) e1) - *((int*) e2);
}
// www.wutianqi.com
int main()
{
    int nCases;
    int num, k, i, j;
    scanf("%d", &nCases;);
    while(nCases--)
    {
        scanf("%d %d", &num;, &k;);
        for(i = 1; i <= num; ++i)
            scanf("%d", &ans;[i]);
        ans[0] = 1000000;    //ans[0]是哨兵,确保ans[0]比其他都大
        for(i = 0; i < k; ++i)   //每次循环都找出下一个排列
        {
            for(j = num; j >= 1 && ans[j-1] > ans[j]; --j)
                ;
            if(j >= 1)
            {
                int nMinLarge = ans[j];
                int nMinId = j;

                //下面找出从ans[j]及其后最小的比ans[j-1]大的元素,并记住其下标
                for(int kk = j; kk <= num; ++kk)
                    if(nMinLarge > ans[kk] && ans[kk] > ans[j-1])
                    {
                        nMinLarge = ans[kk];
                        nMinId = kk;
                    }
                //交换位置
                ans[nMinId] = ans[j-1];
                ans[j-1] = nMinLarge;
                qsort(ans+j, num-j+1, sizeof(int), MyCompare);
            }
            else
                for(j = 1; j <= num; ++j)
                    ans[j] = j;
        }
        for(j = 1; j <= num; ++j)
            printf("%d ", ans[j]);
        printf("\n");

    }
    return 0;
}