POJ2085

Written by    14:00 October 12, 2014 

POJ2085

Inversion
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 4004 Accepted: 1790

Description

The inversion number of an integer sequence a1, a2, . . . , an is the number of pairs (ai, aj) that satisfy i < j and ai > aj . Given n and the inversion number m, your task is to find the smallest permutation of the set { 1, 2, . . . , n }, whose inversion number is exactly m.
A permutation a1, a2, . . . , an is smaller than b1, b2, . . . , bn if and only if there exists an integer k such that aj = bj for 1 <= j < k but ak < bk.

Input

The input consists of several test cases. Each line of the input contains two integers n and m. Both of the integers at the last line of the input is −1, which should not be processed. You may assume that 1 <= n <= 50000 and 0 <= m <= n(n − 1)/2.

Output

For each test case, print a line containing the smallest permutation as described above, separates the numbers by single spaces.

Sample Input

Sample Output

Source

因为题目要求的是符合条件的最小字典排序字符串,所以可以证明答案字符串必须是由递增数列加一个+最大元素+递减数列组成.

比如说:

6 5 7 4 3 2 1 的倒序数就等于 5 7 6 4 3 2 1, 但是根据题意:

A permutation a1, a2, … , an is smaller than b1, b2,…, bn if and only if there exists an integer k such that aj=bj for 1 <= j < k but ak < bk

故前者是大于后者的,所以答案只能是后者.

然后就可以使用贪心算法来求了,给的倒序数是m,首先把n个数逆序排列, 倒序数是n*(n-1)/2,如果把逆序第i个数移到数列列首的话数列的逆序数就会减小(n-i),之前又可知答案数列中最大数之前必须是递增数列,只需要从逆序数列最后一个数开始贪心即可。

Category : acmstudy

Tags :