问题:
大家知道,给出正整数n,则1 到n 这n 个数可以构成n!种排列,把这些排列按照从
小到大的顺序(字典顺序)列出,如n=3 时,列出1 2 3,1 3 2,2 1 3,2 3 1,3 1 2,3 2 1
六个排列。
给出某个排列,求出这个排列的下k 个排列,如果遇到最后一个排列,则下1 排列为第
1 个排列,即排列1 2 3…n。
比如:n = 3,k=2 给出排列2 3 1,则它的下1 个排列为3 1 2,下2 个排列为3 2 1,因
此答案为3 2 1。
输入数据
第一行是一个正整数m,表示测试数据的个数,下面是m 组测试数据,每组测试数据
第一行是2 个正整数n( 1 <= n < 1024 )和k(1<=k<=64),第二行有n 个正整数,是1,2 … n
的一个排列。
输出要求
对于每组输入数据,输出一行,n 个数,中间用空格隔开,表示输入排列的下k 个排列。
输入样例
3
3 1
2 3 1
3 1
3 2 1
10 2
1 2 3 4 5 6 7 8 9 10
输出样例
3 1 2
1 2 3
1 2 3 4 5 6 7 9 8 10
#include <stdio.h>
int MyCompare(const void* e1, const void* e2){
return *((int*) e1) - *((int*) e2);
}
int main(){
int nCases;
scanf("%d", &nCases);
int an[1034], in,n;
while(nCases --){
int k;
scanf("%d %d", &n, &k);
for(in = 0; in < n ; in ++){
scanf("%d", &an[in]);
}
int i,j,index = -1;
for(i = 0; i < k; i ++){
for(j = n -1; j >= 0; j--){
if(an[j - 1] < an[j]){
index = j - 1;
break;
}
}
int m;
if(index == -1 ){
int roop;
for(roop = n ; roop > 0; roop --){
printf("%d ", an[roop -1]);
}
printf("\n");
return 0;
}
int candidate = an[j], index2 = j;
for(m = j; m < n; m++){
if(an[m] > an[index] && an[m] < candidate){
candidate = an[m];
index2 = m;
}
}
int swap = an[index];
an[index] = candidate;
an[index2] = swap;
qsort(an + j, n - j , sizeof(int), MyCompare);
}
}
int i;
for(i = 0; i < n; i++){
printf("%d ", an[i]);
}
printf("\n");
return 0;
}
分享到:
相关推荐
需要杰哥讲解的毕设js代码
C++自制小游戏《杰哥和阿伟》源码(cpp) C++小游戏,由哔哩哔哩的梗制作而成,切勿当真哦~ 游戏内行为请勿模仿! 原创小游戏,请勿转载或整改~ 记得关注@Ender_momo,短时间内将发布制作过程
杰哥两套卷.rar
有跟我一样看不懂代码,只能盲抄来理解的吗,杰哥看到了莫生气我自己现在真写不了好了,今天的案例与while语句有关
本人收集的几套百度笔试题。 doc格式,需要找工作的可以看看
Ceph是一个开源的分布式文件系统。因为它还支持块存储、对象存储,所以很自然的被用做云计算框架openstack或cloudstack整个存储后端。当然也可以单独作为存储,例如部署一套集群作为对象存储、SAN存储、NAS存储等。...
python深度学习-pandas
杰哥应急响应ppt
百度google 笔试题汇总,全是word 文档。对找实习有很多好处的
C语言35页第4题第2小问.exe
大家可以通过这篇文献对控制领域有一个大体的认知。 更多炸裂内容,详见公粽号 :杰哥的无人驾驶便利店。
该文档为配套的【杰哥日常小工具】字符串处理工具的登录效验码,下载工具后可登录解码该文档信息获取管理员或VIP登录码
matlab软件下载:lingo教程数学建模Lingo系列视频(爆肝杰哥): Lingo(1)基础篇:BV1CT4y177qS Lingo(2)入门篇:BV1U
文章目录1 故事的开局2 杰哥的表演2.1 sl2.2 htop2.3 gcp2.4 hollywood2.5 cmatrix2.6 asciiview2.7 ninvaders2.8 bastet2.9 pipe2.10 oneko3 博主的炸弹4 总结 1 故事的开局 周末到了,部门里几个小伙伴约好了一起...
无人驾驶车辆轨迹跟踪控制综述型参考英文文献!大家可以通过这篇文献对控制领域有一个大体的认知。 更多炸裂内容,详见公粽号 :杰哥的无人驾驶便利店
无人驾驶车辆轨迹跟踪控制综述型参考英文文献!大家可以通过这篇文献对控制领域有一个大体的认知。 更多炸裂内容,详见弓粽Hao :杰哥的无人驾驶便利店