企业网站建设公司哪家好,河南旅游集团 网站建设,邵阳做网站哪个公司好,网站怎么使用OD统一考试#xff08;C卷#xff09; 分值#xff1a; 200分 题解#xff1a; Java / Python / C 题目描述
疫情期间#xff0c;需要大家保证一定的社交距离#xff0c;公司组织开交流会议#xff0c;座位有一排共N个座位#xff0c;编号分别为[0…N-1]#xff0c;要… OD统一考试C卷 分值 200分 题解 Java / Python / C 题目描述
疫情期间需要大家保证一定的社交距离公司组织开交流会议座位有一排共N个座位编号分别为[0…N-1]要求员工一个接着一个进入会议室并且可以在任何时候离开会议室。
满足:每当一个员工进入时需要坐到最大社交距离的座位(例如:位置A与左右有员工落座的位置距离分别为2和2位置B与左右有员工落座的位置距离分别为2和3影响因素都为2个位置则认为座位A和B与左右位置的社交距离是一样的)如果有多个这样的座位则坐到索引最小的那个座位。
输入描述
会议室座位总数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与0和9的距离为(4和5),位置5与0和9的距离(5和4)所以位置4和5都是可以选择的座位按照要求需索引最小的那个座位也就是座位4。
seat -2位置2与0和4的距离为(2和2),位置6与4和9的距离(2和3)位置7与4和9的距离(3和2)影响因素都为2个位置按照要求需索引最小的那个座位也就是座位2。leave(4)4号座位的员工离开。
seat- 5员工最后坐在5号座位上。此题为非ACM模式只需要实现 conferenceSeatDistance 方法即可。 题解 这是一个模拟会议室座位安排的问题需要根据特定规则安排员工的座位。 使用有序 Set 来维护已经被坐的座位情况java 代码使用 TreeSet 。并通过插入两个虚拟的座位作为边界来方便计算最大社交距离的座位。进入会议室的算法 使用join方法来计算员工进入会议室时的最佳座位。通过遍历 TreeSet 中相邻的位置计算中间座位的社交距离找到最大距离的座位并插入到 TreeSet 中。座位计算 在主方法中遍历员工的进出顺序根据不同情况调用join方法或者从TreeSet中移除座位。输出 输出最后一个员工坐的位置。 Java
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int seatNum sc.nextInt();sc.nextLine();String seatOrLeaveLine sc.nextLine();String[] c seatOrLeaveLine.substring(1, seatOrLeaveLine.length() - 1).split(, );int[] seatOrLeave new int[c.length];for (int i 0; i c.length; i) {seatOrLeave[i] Integer.parseInt(c[i]);}Main socialDistance new Main();int ans socialDistance.conferenceSeatDistance(seatNum, seatOrLeave);System.out.println(ans);}/*** 计算最后进来的人坐的位置** param seatNum 会议室座位总数* param seatOrLeave 员工的进出顺序* return 最后进来的人坐的位置*/public int conferenceSeatDistance(int seatNum, int[] seatOrLeave) {TreeSetInteger seatTree new TreeSet();// 插入两个虚拟的座位有了这两个个边界方便计算最大社交距离的座位seatTree.add(-2 * (seatNum - 1));seatTree.add(2 * (seatNum - 1));int last -1;for (int t : seatOrLeave) {if (t 1) { // 进来last join(seatTree, seatNum);} else { // 座位 的人离开seatTree.remove(-t);}}return last;}/*** 计算员工进行会议该做的位置** param seatTree 已经被坐的座位情况* param N 会议室座位个数* return -1 没有合适的位置可坐*/public int join(TreeSetInteger seatTree, int N) {// 最大的社交距离int maxDistance 0, idx -1;// 根据 TreeSet key 的有序性遍历所有相邻的位置看中间的座位是否是会议室中社交距离最大的座位IteratorInteger it seatTree.iterator();int pre it.next();while (it.hasNext()) {int cur it.next();int distance (cur - pre) / 2;// 判断在 pre 和 cur 中间坐社交距离是否更大 if (distance maxDistance) {// 坐在 pre 和 pre 中间的位置索引最小的int pos (cur pre) / 2;// 当前 pos 是有效的可坐位置if (0 pos pos N) {idx pos;maxDistance distance;}}pre cur;}// 找到了合适的座位则坐在 idx 位置上if (idx ! -1) seatTree.add(idx);return idx;}
}Python
from itertools import pairwiseclass Solution:def conference_seat_distance(self, seat_num, seat_or_leave):# 记录座位情况self.seat_list [-2 * (seat_num - 1), 2 * (seat_num - 1)]last -1for t in seat_or_leave:if t 1: # 进来last self.join(seat_num)else: # 座位 -t 的人离开self.seat_list.remove(-t)return lastdef join(self, N):max_distance, idx 0, -1# 遍历所有相邻的位置看中间的座位是否是会议室中社交距离最大的座位for pre, cur in pairwise(self.seat_list):distance (cur - pre) // 2# 判断在 pre 和 cur 中间坐社交距离是否更大if distance max_distance:# 坐在 pre 和 pre 中间的位置索引最小的pos (cur pre) // 2# 当前 pos 是有效的可坐位置if 0 pos N:idx posmax_distance distance# 找到了合适的座位则坐在 idx 位置上if idx ! -1:self.seat_list.append(idx)self.seat_list.sort()return idxsolution Solution()
last solution.conference_seat_distance(10, [1, 1, 1, 1, -4, 1])
print(last)
C
#include iostream
#include vector
#include setusing namespace std;class Solution {
public:int conferenceSeatDistance(int seatNum, vectorint seatOrLeave) {setint seatTree;seatTree.insert(-2 * (seatNum - 1));seatTree.insert(2 * (seatNum - 1));int last -1;for (int t : seatOrLeave) {if (t 1) {last join(seatTree, seatNum);} else {seatTree.erase(-t);}}return last;}int join(setint seatTree, int N) {int maxDistance 0, idx -1;auto it seatTree.begin();int pre *it;while (it ! seatTree.end()) {int cur *it;int distance (cur - pre) / 2;if (distance maxDistance) {int pos (cur pre) / 2;if (pos 0 pos N) {idx pos;maxDistance distance;}}pre cur;}if (idx ! -1) seatTree.insert(idx);return idx;}
};❤️华为OD机试面试交流群每日真题分享 加V时备注“华为od加群” 整理题解不易 如果有帮助到您请给点个赞 ❤️ 和收藏 ⭐让更多的人看到。
