首页 > 专题系列 > Java解POJ > POJ 1349 Coding of Permutations [解题报告] Java
2013
11-09

POJ 1349 Coding of Permutations [解题报告] Java

Coding of Permutations

问题描述 :

Write a program that gives us the ordinal position d(P) of any rank-n permutation P=(p1,p2卲n) in the dictionary without producing all the rank-n permutations in order, where pi{1,2,3,…,n},n<=50. When n=4, the whole rank-4 permutation in lexicographical order and the code is shown in the following figure.

For example: if P=(2,3,4,1), then d(P)=10; if P=(4,2,1,3), then d(P)=21.

输入:

(n, P): For more than one input in the input file, one line is for each input ,with -1 at the end. P is in the form of list.

输出:

d(P): It should be in the form of a line with the outputs separated by commas.

样例输入:

(4,(3,2,1,4))
(5,(3,5,1,2,4))
-1

样例输出:

15,67

解题代码:

//* @author: 
import java.util.*;
import java.math.*;

public class Main {
 public static String s;
 public static int []p = new int [51];
 public static int []visit = new int [51];
 public static Vector res = new Vector();
 public static BigInteger []q = new BigInteger [51];
 public static int n;
 static void init()
 {
   q[0] = q[1] = BigInteger.ONE;
   int i;
   for (i = 2; i < 51; i++)
    q[i] = q[i - 1].multiply(new BigInteger (i + ""));
 }

 static void parse()
 {
  int i, j, k, len;
  char ch;
  len = s.length();
  ch = s.charAt(2);
  if (ch >= '0' && ch <= '9')
  {
   n = (ch - '0') + 10 * (s.charAt(1) - '0');
   i = 5;
  }
  else
  {
   n = (s.charAt(1) - '0');
   i = 4;
  }
  k = j = 0;
  while (i < len)
   {
	ch = s.charAt(i);
	if (ch == ',' || ch == ')')
	{
          p[j++] = k;
 	  k = 0;
	}
	else
	  k = k * 10 + (ch - '0');
	i++;
   }
 }

  static void deal()
  {
	BigInteger ans = BigInteger.ONE, temp;
	Arrays.fill(visit, 0);
	int i, j, count;
	for (i = 0; i < n; i++)
	{
          count = 0;
	  for (j = 1; j < p[i]; j++)
	    if (visit[j] == 0)
		 count++;
	    visit[p[i]] = 1;
	    temp = BigInteger.ONE;
	    temp = temp.multiply(new BigInteger (count + "")).multiply(q[n - i - 1]);
	    ans = ans.add(temp);
	 }
	res.addElement(ans);
  }

   static void input()
    {
	Scanner cin = new Scanner (System.in);
	while (cin.hasNext())
	{
	  s = cin.nextLine();
	  if (s.compareTo("-1") == 0)
		break;
	  parse();
	  deal();
	}
	int i, len = res.size();
	for (i = 0; i < len - 1; i++)
	  System.out.print(res.elementAt(i) + ",");
	  System.out.println(res.elementAt(i));
     }
	
   public static void main (String []args)
    {
	init();
	input();
   }
}

  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧