华为od（D卷）最大社交距离
文章目录
- 题目描述
- 输入描述
- 输出描述
- 示例1
- 思路
- 代码
题目描述
疫情期间需要大家保证一定的社交距离，公司组织开交流会议。
座位一排共 N 个座位，编号分别为 [0, N - 1] 。
要求员工一个接着一个进入会议室，并且可以在任何时候离开会议室。
满足：
-
每当一个员工进入时，需要坐到最大社交距离（最大化自己和其他人的距离的座位）；
-
如果有多个这样的座位，则坐到索引最小的那个座位
输入描述
- 会议室座位总数 seatNum 。(1 <= seatNum <= 500)
- 员工的进出顺序 seatOrLeave 数组，元素值为 1，表示进场；元素值为负数，表示出场（特殊：位置 0 的员工不会离开）。
- 例如 - 4 表示坐在位置 4 的员工离开（保证有员工坐在该座位上）
输出描述
最后进来员工，他会坐在第几个位置，如果位置已满，则输出 - 1 。
示例1
输入
10
[1,1,1,1,-4,1]
输出
5
说明
seat -> 0 , 空在任何位置都行，但是要给他安排索引最小的位置，也就是座位 0
seat -> 9 , 要和旁边的人距离最远，也就是座位 9
seat -> 4 , 要和旁边的人距离最远，应该坐到中间，也就是座位 4
seat -> 2 , 员工最后坐在 2 号座位上
leave [4] , 4 号座位的员工离开
seat -> 5 , 员工最后坐在 5 号座位上
思路
注意最大社交距离的判断:
0， 4， 9 位置坐完之后坐的位置是2，而不是6，不是7；
所有社交距离的理解应该是：距离相近左右两人的距离最小值;也就是说 位置2的社交距离是2和位置6，位置7的社交距离是相同的，所以才选择了索引小的2。
那代码上面如何体现呢？ 相邻座位的距离如果相等，或者相差不超过1，那么中间位置的最大社交距离应该是相同的。
代码
public class Demo05 {public static void main(String[] args) {// 座位数int seatNum = 10;// 坐下或者离开int[] seatOrLeave = new int[] {1, 1, 1, 1, -4, 1};//做下的位子编号TreeSet<Integer> seated = new TreeSet<>();for (int i = 0; i < seatOrLeave.length; i++) {int sOrL = seatOrLeave[i];if (sOrL > 0) {// 坐下的位置int seatIndex = -1;if (seated.size() == 0) {seatIndex = 0;} else if (seated.size() == 1) {seatIndex = seatNum - 1;} else {seatIndex = center(seated);}if (seatIndex == -1) {System.out.println(seatIndex);return;} else {seated.add(seatIndex);}//最后一个人if (i == seatOrLeave.length - 1) {System.out.println(seatIndex);}} else {// 离开seated.remove(i);}}}// 查找中间位置public static int center(TreeSet<Integer> seated) {// 两个位置之间的距离最大值int maxLength = 0;// 两个位置之间的距离最大值时，左侧坐下人位置int index = -1;// 遍历时前一个人坐下的位置int before = -1;for (Integer post : seated) {if (before == -1) {before = post;continue;}Integer l = post - before;// 中间没座位if (l == 1) {before = post;continue;}// 相邻座位的距离如果相等，或者相差不超过1，那么中间位置的最大社交距离应该是相同的。if (l > maxLength + 1) {maxLength = l;index = before + maxLength / 2;}before = post;}return index;}
}