2013
11-10

Inversion

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.

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.

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

5 9
7 3
-1 -1

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

import java.util.Scanner;
public class Main{
public static void main(String args[]){

int n,m;
int i,j,k,sum;
Scanner sc=new Scanner(System.in);
while(true)    {
n=sc.nextInt();
m=sc.nextInt();

if(n==-1&&m==-1)break;
sum=0;
for(i=n;i>=1;i--)
{
sum+=(n-i);
if(sum>=m)break;
}
for(j=1;j< i;j++) System.out.printf("%d ",j);
k=m+i-(n-i)*(n-i-1)/2;

System.out.printf("%d",k);

for(j=n;j>=i;j--) if(j!=k) System.out.printf(" %d",j);
System.out.printf("\n");
}
}
}

}

1. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;