hdu1027是要求n个数（1，2，...，n）的第m个排列的问题。
但要注意题目给定的n的取值范围比较大（1<=n<=1000）,而m的范围相对则比较小（m<＝10000）。
对m的范围进行研究7！<10000<8！=40320,可以看出要求的排列数不超过8个数的排列。
由此，可以将n分类讨论：
（1）当n<8时，直接求出n个数的第m个排列。
（2）当n>=8时，先求得8个数(1,2,...,8)的第m个排列，然后在前面补充n-8个数（为1，2，..,n-8），最后一步，把上面8个数(1,2,...,8)的第m个排列每个数字都加上n-8。拼接起来即是所要的答案。
以下红色部分为求t个数的第m个排列。
#include
using namespace std;
///////////////////////
int fac[9],use[9],a[9];
int main()
{int n,m,i,j,t;
t=1;fac[1]=1;fac[0]=0;
for(i=2;i<=8;i++) {t*=i;fac[i]=t;}//1!,2!,...,8!
while(cin>>n>>m)//(1<=N<=1000, 1<=M<=10000<8!=40320).
{
if(n>=8) t=8;//将范围缩小到8个数(1,2,...,8)的第m个排列,前面为1,2,...,n-8
else t=n;
for(i=1;i<=t;i++) use[i]=0;//t个数的第m个排列
for(i=1;i<=t;i++)
{//1,2,3,4 m=22
//i=1,a[1]=4,a[2]=
for(j=1;j<=t;j++)
{
while(use[j]) j++;
if(t-i==0){a[i]=j;use[j]=1;break;}
if(m-fac[t-i]<=0)
{while(use[j]) j++;
a[i]=j;use[j]=1;
// cout< break;
}
else m-=fac[t-i];
}
}
if(n>=8)
{for(i=1;i<=n-8;i++) cout<
for(i=1;i<=t;i++) a[i]+=n-8;
}
for(i=1;i<=t-1;i++) cout<
}
return 1;
}
阅读(1501) | 评论(0) | 转发(0) |
