#P2085. Inversion

Inversion

题目描述:

给定一个整数序列 a1a₁, a2a₂, ..., anaₙ,其逆序数定义为满足 ii < jjaiaᵢ > ajaⱼ 的数对 (aiaᵢ, ajaⱼ) 的个数。给定整数 nn 和逆序数 mm,你的任务是找到集合 {11, 22, ..., nn} 的最小排列,使得该排列的逆序数恰好为 mm

排列 a1a₁, a2a₂, ..., anaₙ 比排列 b1b₁, b2b₂, ..., bnbₙ 小,当且仅当存在一个整数 kk,使得对于所有 11jj < kkajaⱼ = bjbⱼ,但 akaₖ < bkbₖ

输入格式:

输入包含多个测试用例。每行输入两个整数 nnmm。最后一行输入的两个整数均为 1-1,表示输入结束,不应处理该行。你可以假设 11nn500005000000mmn(n1)/2n(n − 1)/2

输出格式:

对于每个测试用例,输出一行包含满足条件的最小排列,数字之间用单个空格分隔。

示例输入:

5 9
7 3
-1 -1

示例输出:

4 5 3 2 1
1 2 3 4 7 6 5

来源:

2004年上海赛区初赛