首页 > 专题系列 > Java解POJ > POJ 3640 Conformity [解题报告] Java
2013
11-13

POJ 3640 Conformity [解题报告] Java

Conformity

问题描述 :

Frosh commencing their studies at Waterloo have diverse interests, as evidenced by their desire to take various combinations of courses from among those available.

University administrators are uncomfortable with this situation, and therefore wish to offer a conformity prize to frosh who choose one of the most popular combinations of courses. How many frosh will win the prize?

输入:

The input consists of several test cases followed by a line containing 0. Each test case begins with an integer 1 ≤ n ≤ 10000, the number of frosh. For each frosh, a line follows containing the course numbers of five distinct courses selected by the frosh. Each course number is an integer between 100 and 499.

The popularity of a combination is the number of frosh selecting exactly the same combination of courses. A combination of courses is considered most popular if no other combination has higher popularity.

输出:

For each line of input, you should output a single line giving the total number of students taking some combination of courses that is most popular.

样例输入:

3
100 101 102 103 488
100 200 300 101 102
103 102 101 488 100
3
200 202 204 206 208
123 234 345 456 321
100 200 300 400 444
0

样例输出:

2
3

解题代码:

//* @author 洪晓鹏<[email protected]>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Main {

/**
 * @param args
 * @throws IOException
 * @throws NumberFormatException
 */
public static void main(String[] args) throws NumberFormatException,
	IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  while (true) {
	Map< String, Integer> map = new HashMap< String, Integer>();
	int max = 0;
	int n = Integer.parseInt(br.readLine());
	if (n == 0)
		break;
	for (int i = 0; i < n; i++) {
		String s = br.readLine();
		String[] array = s.split(" ");
		Arrays.sort(array);
		String key = new String();
		for (int j = 0; j < array.length; j++) {
			key += array[j];
		}
		// System.out.println("key:"+key);
		if (map.get(key) == null)
			map.put(key, 1);
		else {
			// System.out.println("here");
			map.put(key, map.get(key) + 1);
		}
		if (max < map.get(key))
			max = map.get(key);
	}
	int result = 0;
	Set set = map.keySet();
	for (String s : set) {
		if (max == map.get(s))
			result += max;
	}
	System.out.println(result);
  }
 }

}

  1. [email protected]

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  3. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience