百练oj 1833 排列

咳咳,这道模拟题的思路有点。。。明天补上。
地址: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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注