问题2133--构造逆序数列(inversion)

2133: 构造逆序数列(inversion)

时间限制: 1 Sec  内存限制: 128 MB
提交: 54  解决: 25
[提交] [状态] [讨论版] [命题人:]

题目描述

一个长度为n的整数序列{a1, a2, a3, … an},对于任意一对元素,如果i<j,且ai>aj,则称(ai, aj)为一对逆序对。根据这个定义,我们可以统计这个整数序列有多少个逆序对。
例如n=4, 序列为{3, 2, 4, 1},逆序对有4个,分别为(3, 2), (3, 1), (2, 1), (4, 1)。
现在BSNY想构造n个元素,包含m个逆序对的序列,这个方案有很多,为了简化方案,BSNY要求这个序列是[1, n]排列,即序列的元素由[1, n]构成;同时,BSNY要求这个排列字典序最小。聪明的你,可以帮助BSNY构造这个逆序数列吗?

输入

输入n, m

输出

输出n个整数,空格隔开

样例输入2:
7 3
样例输出2:
1 2 3 4 7 6 5

样例输入 Copy

5 9

样例输出 Copy

4 5 3 2 1

提示

30%的数据   1<=n<=20
60%的数据   1<=n<=2000
100%的数据  1<=n<=100000,    0<=m<=n*(n-1)/2

来源/分类