首页 > 数据结构 > Hash表 > POJ 1250 Tanning Salon [解题报告] Java
2013
11-09

POJ 1250 Tanning Salon [解题报告] Java

Tanning Salon

问题描述 :

Tan Your Hide, Inc., owns several coin-operated tanning salons. Research has shown that if a customer arrives and there are no beds available, the customer will turn around and leave, thus costing the company a sale. Your task is to write a program that tells the company how many customers left without tanning.

输入:

The input consists of data for one or more salons, followed by a line containing the number 0 that signals the end of the input. Data for each salon is a single line containing a positive integer, representing the number of tanning beds in the salon, followed by a space, followed by a sequence of uppercase letters. Letters in the sequence occur in pairs. The first occurrence indicates the arrival of a customer, the second indicates the departure of that same customer. No letter will occur in more than one pair. Customers who leave without tanning always depart before customers who are currently tanning. There are at most 20 beds per salon.

输出:

For each salon, output a sentence telling how many customers, if any, walked away. Use the exact format shown below.

样例输入:

2 ABBAJJKZKZ
3 GACCBDDBAGEE
3 GACCBGDDBAEE
1 ABCBCA
0

样例输出:

All customers tanned successfully.
1 customer(s) walked away.
All customers tanned successfully.
2 customer(s) walked away.

解题代码:

//* @author 洪晓鹏<[email protected]>
	import java.util.ArrayList;
import java.util.HashSet;
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 num = in.nextInt();
			if (num == 0)
				break;
			String customers = in.next();
			int leftCustomer = 0;
			Set customerSet = new HashSet();
			for (int i = 0; i < customers.length(); i++) {
				int size = customerSet.size();
				if (size >= num) {
					if (customerSet.contains(customers.charAt(i))) {
						customerSet.remove(customers.charAt(i));
						continue;
					}
					leftCustomer++;
					int index = customers.indexOf(customers.charAt(i), i + 1);
					if (index != -1)
						customers = customers.substring(0, index)
								+ customers.substring(index + 1);
				} else {
					if (customerSet.contains(customers.charAt(i))) {
						customerSet.remove(customers.charAt(i));
					} else
						customerSet.add(customers.charAt(i));
				}
			}
			if (leftCustomer == 0)
				System.out.println("All customers tanned successfully.");
			else
				System.out.println(leftCustomer + " customer(s) walked away.");
		}
	}
}

  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。