Blog·Tanky WooABOUTRSS

百练oj 1833 排列

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

咳咳,这道模拟题的思路有点。。。明天补上。 地址:http://poj.pku.edu.cn/problem/1833/

#include
#include

#include
#include
#include
#include
using namespace std;

#define MAX_NUM 1030
int an[MAX_NUM];

int MyCompare(const void* e1, const void* e2)
{
    return *((int*)e1) - *((int*)e2);
}

int main()
{
    int i, j;
    int nCases;
    int n, k;
    scanf("%d", &nCases);
    while(nCases--)
    {
        scanf("%d%d", &n, &k);
        for(i = 1; i <= n; i++)
            scanf("%d", &an[i]);
        an[0] = 10000;

        for(i = 0; i < k; i++)
        {
            for(j = n; j >= 1 && an[j] < an[j-1]; j--)
                ;
            if( j >= 1)
            {
                int nMinLarger = an[j];
                int nMinIdx = j;
                for(int kk = j; kk <= n; kk++)
                    if(nMinLarger > an[kk] && an[kk] > an[j-1])
                    {
                        nMinLarger = an[kk];
                        nMinIdx = kk;
                    }
                an[nMinIdx] = an[j-1];
                an[j-1] = nMinLarger;

                qsort(an+j, n-j+1, sizeof(int), MyCompare);
            }
            else
                for(j = 1; j <= n; j++)
                    an[j] = j;
        }
        for(j = 1; j <= n; j++)
            printf("%d ", an[j]);
        putchar('\n');
    }
    return 0;
}