首页 > 数据结构 > Hash表 > POJ 2470 Ambiguous permutations [解题报告] Java
2013
11-11

POJ 2470 Ambiguous permutations [解题报告] Java

Ambiguous permutations

问题描述 :

Some programming contest problems are really tricky: not only do they require a different output format from what you might have expected, but also the sample output does not show the difference. For an example, let us look at permutations.

A permutation of the integers 1 to n is an ordering of these integers. So the natural way to represent a permutation is to list the integers in this order. With n = 5, a permutation might look like 2, 3, 4, 5, 1.

However, there is another possibility of representing a permutation: You create a list of numbers where the i-th number is the position of the integer i in the permutation. Let us call this second possibility an inverse permutation. The inverse permutation for the sequence above is 5, 1, 2, 3, 4.

An ambiguous permutation is a permutation which cannot be distinguished from its inverse permutation. The permutation 1, 4, 3, 2 for example is ambiguous, because its inverse permutation is the same. To get rid of such annoying sample test cases, you have to write a program which detects if a given permutation is ambiguous or not.

输入:

The input contains several test cases.

The first line of each test case contains an integer n (1 <= n <= 100000). Then a permutation of the integers 1 to n follows in the next line. There is exactly one space character between consecutive integers. You can assume that every integer between 1 and n appears exactly once in the permutation.

The last test case is followed by a zero.

输出:

For each test case output whether the permutation is ambiguous or not. Adhere to the format shown in the sample output.

样例输入:

4
1 4 3 2
5
2 3 4 5 1
1
1
0

样例输出:

ambiguous
not ambiguous
ambiguous

温馨提示:

Huge input,scanf is recommended.

解题代码:

//* @author 洪晓鹏<[email protected]>
//读大数据 buffered

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
 public static void main(String[] args) throws IOException {
		
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

   while (true) {
	int n = Integer.parseInt(in.readLine());
	if (n == 0)
		break;
	//StringTokenizer st = new StringTokenizer(in.readLine()," ");
	String s = in.readLine();
	String[] sArray=s.split(" ");
	Map< Integer, Integer> map = new HashMap< Integer, Integer>();
	int[] array = new int[n];
	int i = 0;
//	while(st.hasMoreTokens()) {
//		int key = Integer.parseInt(st.nextToken());
//		array[i] = key;
//		map.put(key, i+1);
//		i++;
//	}
//	int sl = sArray.length;
	//System.out.println(sl);
	for(i = 0; i< n; i++){
		int key = Integer.parseInt(sArray[i]);
		array[i] = key;
		map.put(key, i+1);
	}
	int count = 0;
	for (i = 0; i < n; i++) {
		if (map.get(i+1) == array[i])
			count++;
		else
			break;
		//System.out.println(array[i]+" "+map.get(i+1));
	
	}
	if (count == n)
		System.out.println("ambiguous");
	else
		System.out.println("not ambiguous");
		
  }
 }
}

  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  2. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?