Inversion

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 4176		Accepted: 1857

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

4 5 3 2 1

1 2 3 4 7 6 5

Source

Shanghai 2004 Preliminary

题目大意：

给出n和m，求1~n组成的序列中逆序对数为m的最小一个序列。

有多组数据，-1 -1表示输入结束。

思路：

首先，ans一定会是个先上升再下降的数列。（如右图）

而且，上升的序列是逐个加一，抛出尾数，即折点数。

而下降的序列就是剩下的数也抛去折点数，依次输出。

因此，只需要求出折点数x和下降序列的长度k即可。

右图中数据的x，k依次为：

9,3；

10,3；

7,4；

10,3；

3,4。

代码实现：

 #include<cstdio>

 int n,m,k,x;

 bool v;

 void write(bool& v,int x){

     if(v) v=false;

     else putchar(' ');

     printf("%d",x);

 }

 int main(){

     while(scanf("%d%d",&n,&m)&&n!=-){

         k=;

         for(;k*(k+)<*m;k++);

         x=m-k*(k-)/+n-k;

         v=true;

         for(int i=;i<=n-k-;i++) write(v,i);

         write(v,x);

         for(int i=n;i>=n-k;i--)

         if(i!=x) write(v,i);

         putchar('\n');

     }

     return ;

 }

题目来源：POJ

巴特西

Inversion

最新文章

热门文章