首页 > 数据结构 > Hash表 > POJ 2028 When Can We Meet? [解题报告] Java
2013
11-10

POJ 2028 When Can We Meet? [解题报告] Java

When Can We Meet?

问题描述 :

The ICPC committee would like to have its meeting as soon as possible to address every little issue of the next contest. However, members of the committee are so busy maniacally developing (possibly useless) programs that it is very difficult to arrange their schedules for the meeting. So, in order to settle the meeting date, the chairperson requested every member to send back a list of convenient dates by E-mail. Your mission is to help the chairperson, who is now dedicated to other issues of the contest, by writing a program that chooses the best date from the submitted lists. Your program should find the date convenient for the most members. If there is more than one such day, the earliest is the best.

输入:

The input has multiple data sets, each starting with a line containing the number of committee members and the quorum of the meeting.

N Q

Here, N, meaning the size of the committee, and Q meaning the quorum, are positive integers. N is less than 50, and, of course, Q is less than or equal to N.

N lines follow, each describing convenient dates for a committee member in the following format.

M Date1 Date2 … DateM

Here, M means the number of convenient dates for the member, which is an integer greater than or equal to zero. The remaining items in the line are his/her dates of convenience, which are positive integers less than 100, that is, 1 means tomorrow, 2 means the day after tomorrow, and so on. They are in ascending order without any repetition and separated by a space character. Lines have neither leading nor trailing spaces.

A line containing two zeros indicates the end of the input.

输出:

For each data set, print a single line containing the date number convenient for the largest number of committee members. If there is more than one such date, print the earliest. However, if no dates are convenient for more than or equal to the quorum number of members, print 0 instead.

样例输入:

3 2
2 1 4
0
3 3 4 8
3 2
4 1 5 8 9
3 2 5 9
5 2 4 5 7 9
3 3
2 1 4
3 2 5 9
2 2 4
3 3
2 1 2
3 1 2 9
2 2 4
0 0

样例输出:

4
5
0
2

解题代码:

//* @author 洪晓鹏<[email protected]>
import java.awt.Label;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {
 public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
   while (true) {

	int n = in.nextInt();
	int q = in.nextInt();
	if ((n | q) == 0)
          break;
	  Map< Integer, Integer> map = new HashMap< Integer, Integer>();
	  for (int i = 0; i < n; i++) {
	   int m = in.nextInt();
	   for (int j = 0; j < m; j++) {
	   int temp = in.nextInt();
		if (map.get(temp) == null)
			map.put(temp, 1);
		else
			map.put(temp, map.get(temp) + 1);
		}
	  }
	Set< Integer> key = map.keySet();
	int max = 0;
	int keyValue = 0;
	for (Integer i : key) {
		if (map.get(i) > max) {
			max = map.get(i);
			keyValue = i;
		}
		if (map.get(i) == max) {
			if (i <= keyValue)
	                  keyValue = i;
		}
	}
	if (max < q)
	    System.out.println(0);
	else
            System.out.println(keyValue);
	}
  }
}

  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.