首页 > 专题系列 > Java解POJ > POJ 2085 Inversion [解题报告] Java
2013
11-10

POJ 2085 Inversion [解题报告] Java

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;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。