http://acm.pku.edu.cn/JudgeOnline/problem?id=2085 給定整數(shù)N，和一個(gè)序列的逆序數(shù)M，求以1，2...N為元素，逆序?yàn)镸，且按字典序最小的那個(gè)序列。
只要知道這樣一個(gè)事實(shí)：一個(gè)序列的逆序唯一決定了這個(gè)序列。
例如：序列1，4，3，2的逆序?yàn)?--0，2--2，3--1，4--0，可以用一個(gè)四維坐標(biāo)來(lái)表示（0，2，1，0），第i維的數(shù)是 i 在原序列中的逆序數(shù)，取值范圍是0，1...4-i。
為解決這個(gè)問(wèn)題，以N=4,逆序數(shù)M=5為例。
對(duì)這個(gè)問(wèn)題可以采取貪心策略。
首先，如果所求序列以1為首，則1的逆序?yàn)?，可以從上表看出此時(shí)序列的逆序數(shù)最多為2+1=3<5，不滿足。考慮以2為首，序列的逆序最多為3+1<5，不滿足。
考慮以3為首，可見(jiàn)當(dāng)1的逆序?yàn)?，2的逆序?yàn)?，4的逆序?yàn)?時(shí)滿足要求，這時(shí)1，2，4均為最大逆序，因而只能排列為4，2，1，加上首數(shù)，所求序列為3，4，2，1。
若M=3，采取同樣的貪心策略，可求得結(jié)果為1，4，3，2。
依此思路，可以得到所求序列關(guān)于N，M的關(guān)系式，具體如下：
1，2，3，...N-P, N-((p-1)*p/2-M), N , N-1...N-P+1.(P是滿足（P-1）*P/2>=M的最小值)。
代碼就容易多了。
關(guān)于更多排列的內(nèi)容可參考：
/Files/sdz/s.doc
#include <stdio.h>
int main(int argc, char *argv[])
{
int n,m;
int p,temp,i;
while(scanf("%d%d",&n,&m) && n>0)
{
p=1;
while((p*(p-1))/2<m)p++;
temp=(p*(p-1))/2;
for(i=1;i<=n-p;i++)
printf("%d ",i);
printf("%d ",n-temp+m);
for(i=n;i>=n-p+1;i--)
{
if(i!=n-temp+m)
printf("%d ",i);
}
printf("\n");
}
return 0;
}