这篇博客是从旧博客 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;
}