1 12 12 22 32 43 10Sample Output111 222 12 3 1我的思路 : 看了标准代码懵逼好久最终搞定。按照数字大小顺序排序,
可以发现,输出的序列第一个是m除以n个数的排序数,比如2有2种组合,3每次有5种组合,如果组合数以数组a(n)表示,则有a(n)=(n-1)*a(n-1)+1的规律
剩下的依序输出,比如输入的n和m是3 10,则第一个输出的应当是10/5,考虑到3有5种组合,但是第五种是以1开头的最后一种序列,所以,m=10时,其实是2开头的最后一种序列。若是m=11,虽然m/5=2,但是已经是3开头的序列了,所以,计算第一个输出的数时,应该是t=m/n组合数+m%n组合数?1:0;意思是如果求余不为0,加一,这样就符合实际情况。以此类推,每当输出一个t,应当将t从常数数组内去除,也就是将t之后的数全部提前一位。
以下是我的代码:#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<iomanip>#include<string.h>using namespace std;int main( ){ int a[21] = {0}, i; long long p[21] = {0}, n, m, t; while (cin >> n >> m) { for (i = 0; i < 21; i++) a[i] = i; p[1] = 1; for (i = 2; i < 21; i++) p[i] = p[i-1] * (i - 1) + 1; //计算出每个数字有几种排列,如N=1时,数字1开头有1种排列; //N=2时,数字1开头有2种排列;N=3时, 有5种排列。 while (n-- && m) { t = m / p[n+1] + (m % p[n+1] ? 1 : 0); //计算出该m是在哪一组 cout << a[t]; for (i = t; i <= n; i++) a[i] = a[i+1];//删去已经排列那个数字 m = m - ((t - 1) * p[n + 1] + 1); // 去掉前面的小于t开头的组合,且将去掉一个仅有t的集合 if (m==0) cout << "/n"; else cout << " "; } } return 0;}
新闻热点
疑难解答