华为南研所2014春季机试题目-2不能入住的房客数

不能入住的房客数

题目描述：

       有一个宾馆，只有m个房间（room），有房客（A~Z）到来时，若有空房间则可以立即入住；没有空房间则不能入住，旅客可以选择立即离开或者等待空房间；

假设给定了各个旅客到达和离开的顺序（如HFBJJBKFHMMSSLPWWPLK），问有多少个旅客没能入住。

 

要求：

输入：房间数  旅客到达离开的序列

输出：最终没能入住的旅客数

 

样例：

输入：3  HFBJJBKFHMMSSLPWWPLK

输出：2

 

思路：

用List集合模拟房间，按旅客到达离开次序进行遍历，来一个旅客首先判断是否已在房间里，若在代表遍历到的是离开的标志；若不在，则看是否有空房间，有则添加进去；

 

package com.liuhao;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class UserNORooms {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int room = scan.nextInt();// 房间数
		String users = scan.next();// 旅客到来离开顺序

		// 采用List方便添加和删除
		List inList = new ArrayList();// 存放已经住进的旅客

		int result = 0;// 存放最终的不能入住的旅客数
		
		// 按旅客的到来顺序依次遍历，模拟场景
		for (int i = 0; i < users.length(); i++) {
			// 先判断是否在房间里，若在则将其删除
			if (isInRoom(inList, users.charAt(i))) {
				inList.remove(getRoom(inList, users.charAt(i)));
			}
			// 不在，看房间是否注满，没满则添加
			else if (inList.size() < room) {
				inList.add(users.charAt(i));
			}
			// 不能入住，结果加一
			else {
				result++;
				continue;
			}
		}

		System.out.println(result / 2);// 没能入住的在遍历过程中算了两次
	}

	// 判断旅客是否在住
	private static boolean isInRoom(List inList, char user) {
		boolean temp = false;

		for (int i = 0; i < inList.size(); i++) {
			if (user == (char) inList.get(i)) {
				temp = true;
				break;
			}
		}

		return temp;
	}

	// 返回旅客在住的房间号
	private static int getRoom(List inList, char user) {
		int temp = 0;
		for (int i = 0; i < inList.size(); i++) {
			if (user == (char) inList.get(i)) {
				temp = i;
				break;
			}
		}
		return temp;
	}

}