855.Exam Room
855.Exam Room
在考场里，一排有 N 个座位，分别编号为 0, 1, 2, ..., N-1 。 当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。) 返回 ExamRoom(int N) 类，它有两个公开的函数：其中，函数 ExamRoom.seat() 会返回一个 int （整型数据），代表学生坐的位置；函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。请确保每次调用 ExamRoom.leave(p) 时都有学生坐在座位 p 上。
示例：
输入：["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
输出：[null,0,9,4,2,null,5]
解释：
ExamRoom(10) -> null
seat() -> 0，没有人在考场里，那么学生坐在 0 号座位上。
seat() -> 9，学生最后坐在 9 号座位上。
seat() -> 4，学生最后坐在 4 号座位上。
seat() -> 2，学生最后坐在 2 号座位上。
leave(4) -> null
seat() -> 5，学生最后坐在 5 号座位上。
提示：
1 <= N <= 10^9
在所有的测试样例中 ExamRoom.seat() 和 ExamRoom.leave() 最多被调用 10^4 次。
调用 ExamRoom.leave(p) 时需要确保当前有学生坐在座位 p 上。
方法：
- 在构造函数中保存座位长度。
- 创建座位时，首先判断是否没人，如果是空的，则直接返回0，并将0压入作为site，表示0号位置有人。
- 判断是否只有一个人，当只有一个人时，判断当前座位号是否超过了座位号中位数，如果超过了或刚好相等，则应该插入0号座位，如果没有，则在末尾插入最大座位号。
- 需要找出两两相邻座位距离的最大值，即插入后和相邻座位距离最大值。先判断首末座位号，找出第一个座位号距0号座位的距离并和最后一个座位号与n-1的距离比较，求出最大值。
- 然后一次判断中间两两相邻的座位插入后的距离，求出最大距离。
- 如果最大距离为site[0]则说明应当插0号在首位，返回。
- 如果最大距离为某两个座位之间，则插入相邻两座位号均值，并返回插入值。
- 如果最大距离为site[site.size()-1]则说明应该插在末尾。返回n-1。（这个判断一定要在末尾，因为当距离相同时，优先坐小号）
- leave函数则直接遍历一遍，erase掉该位置的座位号。
class ExamRoom {
public:
int n;
vector<int> site;
ExamRoom(int N) {
n=N;
}
int seat() {
if(site.empty())
{
site.push_back(0);
return 0;
}
if(site.size()==1)
{
if(site[0] >= n/2)
{
site.insert(site.begin(),0);
return 0;
}
else
{
site.push_back(n-1);
return n-1;
}
}
int dis=max(site[0],n-1-site[site.size()-1]);
for(int i=0;i<site.size()-1;i++) dis = max(dis, (site[i+1]-site[i])/2);
if(dis == site[0])
{
site.insert(site.begin(),0);
return 0;
}
for(int i=0;i<site.size()-1;i++)
if((site[i+1]-site[i])/2 == dis)
{
site.insert(site.begin()+i+1,(site[i]+site[i+1])/2);
return site[i+1];
}
// if(dis == n-1- site[site.size()-1])
// {
site.push_back(n-1);
return n-1;
// }
}
void leave(int p) {
for(int i=0;i<site.size();i++) if(site[i] == p) site.erase(site.begin()+i);
}
};
/**
* Your ExamRoom object will be instantiated and called as such:
* ExamRoom obj = new ExamRoom(N);
* int param_1 = obj.seat();
* obj.leave(p);
*/
Last modified 11mo ago