原 初学ACM - 组合数学基础题目PKU
题目链接：http://poj.org/problem?id=1833
题意说的很清楚，就是找出当前排列后的第k个排列。
很容易的，就能利用STL的next_permulation()函数写出一个答案：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int data[1025];
int main(){
int n,k,m;
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&n,&k);
for(int i=0; i<n; i++)
{
scanf("%d",&data[i]);
}
while(k--)
next_permutation(data,data+n);
for(int i=0; i<n; i++)
{
printf("%d ",data[i]);
}
putchar('\n');
}
return 0;
}然而提交上去，会提示超时...
有些摸不着头脑，因为网上AC的代码基本也都是调用k次next_permulation写的。
然后看到了这篇文章：Poj 1833 排列 —— 一道水题的凌乱
才明白，原来多次调用printf函数也会超时。。
于是，就一次把它复制到输出缓冲区吧。
#include <iostream>
#include <cstdio>
#include <iterator>
#include <algorithm>
using namespace std;
int data[1025];
int main()
{
int n,k,m;
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&n,&k);
for(int i=0; i<n; i++)
{
scanf("%d",&data[i]);
}
while(k--)
next_permutation(data,data+n);
copy(data,data+n-1,ostream_iterator<int>(cout," "));
cout<<data[n-1]<<endl;
}
return 0;
}这时就AC了，只用了500ms，说明调用printf至少消耗了500ms的时间。不过同样的代码，使用C++模式提交就跑了985ms，几乎是压线跑完。。
Run ID User Problem Result Memory Time Language Code Length Submit Time
14813838 Arclabs001 1833 Accepted 696K 500MS G++ 477B 2015-10-14 17:41:22
14813836 Arclabs001 1833 Accepted 204K 985MS C++ 477B 2015-10-14 17:40:55
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
