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

阳7394

不能入住的房客数

题目描述：
　　       有一个宾馆，只有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;
}
}