企业官网建设流程全解析

可以免费建设网站,上海设计网站开发,免费素材库网,国内知名软件开发公司(新卷,200分)- 最大社交距离#xff08;Java JS Python C#xff09;题目描述疫情期间需要大家保证一定的社交距离#xff0c;公司组织开交流会议。座位一排共 N 个座位#xff0c;编号分别为 [0, N - 1] 。要求员工一个接着一个进入会议室#xff0c;并…(新卷,200分)- 最大社交距离Java JS Python C题目描述疫情期间需要大家保证一定的社交距离公司组织开交流会议。座位一排共 N 个座位编号分别为 [0, N - 1] 。要求员工一个接着一个进入会议室并且可以在任何时候离开会议室。满足每当一个员工进入时需要坐到最大社交距离最大化自己和其他人的距离的座位如果有多个这样的座位则坐到索引最小的那个座位。输入描述会议室座位总数 seatNum1 ≤ seatNum ≤ 500员工的进出顺序 seatOrLeave 数组元素值为 1表示进场元素值为负数表示出场特殊位置 0 的员工不会离开例如 -4 表示坐在位置 4 的员工离开保证有员工坐在该座位上输出描述最后进来员工他会坐在第几个位置如果位置已满则输出-1。用例输入10[1, 1, 1, 1, -4, 1]输出5说明seat - 0,空在任何位置都行但是要给他安排索引最小的位置也就是座位 0seat - 9,要和旁边的人距离最远也就是座位 9seat - 4,要和旁边的人距离最远应该坐到中间也就是座位 4seat - 2,员工最后坐在 2 号座位上leave[4], 4 号座位的员工离开seat - 5,员工最后坐在 5 号座位上题目解析我的解题思路如下首先定义一个集合 seatIdx 用于记录已经坐人的座位号。然后遍历第二行输入的员工出入顺序数组如果遍历出来的数组元素infoinfo值为负数则坐在 -info 座位号的员工要离开我们应该将 -info 从 seatIdx 中去除。info值为正数则有一个员工要进来入座我们需要找到具有最大社交距离的座位给这个员工假设座位使用情况如[1, 0, 0, 1, 0 , 0, 0]其中1代表有人坐0代表没人坐。我们观察其中的连续空闲座位情况连续空闲座位的左右边界有如下情况1、左右边界都无人此时必然是所有座位都为空[0, 0, 0, 0, 0]因为题目说位置 0 的员工不会离开2、左右边界都有人[1, 0, 0, 1,0 , 0, 0]3、左边界有人右边界无人[1, 0, 0,1, 0 , 0, 0]4、左边界无人右边界有人本题不存在这种情况因为题目说位置 0 的员工不会离开如果有员工要入座则检查如果seatIdx.size 0则说明所有座位都是空的此时对应员工直接做到第0个座位如果seatIdx.size 1则说明只有一个座位坐了人那么该座位肯定是第0个座位因此当前要入座的员工最大社交距离位置是第 seatNum - 1 个位置如果seatIdx.size 1则此时我们需要遍历seatIdx即遍历出哪些座位做了人一次遍历两个即获得了连续空闲座位的左右边界假设左边界是left右边界是right那么连续空闲座位长度dis right - left - 1如下图所示此时该连续空闲座位中选一个具有最大社交距离的位置通过图示我们可以很容易判断出是第4个位置。求解时我们可以先根据dist求出最大社交距离curSeatDis为curSeatDis dis / 2如果 dis 是偶数则还需要 curSeatDis - 1比如下图dis 8座位4的社交距离 8 / 2 - 1 3如果 dis 是奇数则不需要做处理比如下图得到当前空闲区域的最大社交距离后我们即可求出当前空闲区域具备最大社交距离的座位号curSeatIdx left curSeatDis 1如果当前座位情况存在多个连续空闲座位区域比如[1, 0, 0, 0, 1, 0, 0, 1, 0 , 0 , 0, 0 , 1]此时我们应该按照上面逻辑求出每一个空闲区域的最大社交距离如果对应空闲区域的最大社交距离更大则对应空闲区域可以得到更优的座位。题目说如果有多个这样的座位则坐到索引最小的那个座位。因此只有当前空闲区域的最大社交距离严格大于前面的才能更新最优座位号。这样可以保证出现相同最大社交距离时可以保留索引较小的座位号。另外还有一种特殊情况比如下面座位使用情况[1, 0, 0, 0, 1, 0, 0, 0]此时进来一个员工入座的话则选择最后一个座位社交距离更大即如果最后一个座位空闲那么选择坐最后一个座位的社交距离计算公式是不同于之前左右边界都有人的情况的此时最大社交距离curSeatDis为curSeatDis seatNum - 1 - seatIdx.getLast - 1我们应该考虑到这种情况。另外本题还需要考虑坐满的情况。更多细节请看代码实现。JS算法源码const rl require(readline).createInterface({ input: process.stdin }); var iter rl[Symbol.asyncIterator](); const readline async () (await iter.next()).value; void (async function () { const seatNum parseInt(await readline()); const seatOrLeave JSON.parse(await readline()); console.log(getResult(seatNum, seatOrLeave)); })(); function getResult(seatNum, seatOrLeave) { // 记录已经坐人位置的序号 let seatIdx []; // 记录题解 let lastSeatIdx -1; // 遍历员工的进出顺序 for (let info of seatOrLeave) { // 如果当前元素值为负数表示出场特殊位置 0 的员工不会离开 // 例如 -4 表示坐在位置 4 的员工离开保证有员工坐在该座位上 if (info 0) { const leaveIdx -info; seatIdx seatIdx.filter((idx) idx ! leaveIdx); continue; } // 如果当前元素值为 1表示进场 // 如果没有空闲位置则坐不下 if (seatIdx.length seatNum) { lastSeatIdx -1; continue; } if (seatIdx.length 0) { // 当前人员进场前座位上没有人则当前人员是第一个进场的直接坐第0个位置 seatIdx.push(0); lastSeatIdx 0; } else if (seatIdx.length 1) { // 当前人员进场前座位上只有一个人那么这个人肯定坐在第0个位置则当前进场的人坐在 seatNum - 1 位置才能离 0 位置最远 seatIdx.push(seatNum - 1); lastSeatIdx seatNum - 1; } else { // 记录具有最大社交距离的座位号 let bestSeatIdx -1; // 记录最大社交距离 let bestSeatDis -1; let left seatIdx[0]; // 左边界 for (let i 1; i seatIdx.length; i) { const right seatIdx[i]; // 右边界 // 连续空闲座位区域的长度 const dis right - left - 1; // 如果连续空闲座位区域长度为0则无法坐人此时遍历下一个连续空闲座位区域 // 如果连续空闲座位区域长度大于0则可以坐人 if (dis 0) { // 当前空闲区域能产生的最大社交距离 const curSeatDis Math.floor(dis / 2) - (dis % 2 0 ? 1 : 0); // 当前空闲区域中具备最大社交距离的位置 const curSeatIdx left curSeatDis 1; // 保留最优解 if (curSeatDis bestSeatDis) { bestSeatDis curSeatDis; bestSeatIdx curSeatIdx; } } left right; } // 如果最后一个座位即第 seatNum - 1 号座位没有坐人的话比如 1 0 0 0 1 0 0 0 0此时最后一段空闲区域是没有右边界的需要特殊处理 if (seatIdx.at(-1) seatNum - 1) { // 此时可以直接坐到第 seatNum - 1 号座位最大社交距离为 curSeatDis const curSeatDis seatNum - 1 - seatIdx.at(-1) - 1; const curSeatIdx seatNum - 1; // 保留最优解 if (curSeatDis bestSeatDis) { bestSeatIdx curSeatIdx; } } // 如果能坐人则将坐的位置加入seatIdx中 if (bestSeatIdx 0) { seatIdx.push(bestSeatIdx); seatIdx.sort((a, b) a - b); } // 假设当前人就是最后一个人那么无论当前人是否能坐进去都更新lastSeatIdx bestSeatIdx lastSeatIdx bestSeatIdx; } } return lastSeatIdx; }Java算法源码import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int seatNum Integer.parseInt(sc.nextLine()); String tmp sc.nextLine(); int[] searOrLeave Arrays.stream(tmp.substring(1, tmp.length() - 1).split(, )) .mapToInt(Integer::parseInt) .toArray(); System.out.println(getResult(seatNum, searOrLeave)); } public static int getResult(int seatNum, int[] seatOrLeave) { // 记录已经坐人位置的序号 ArrayListInteger seatIdx new ArrayList(); // 记录题解 int lastSeatIdx -1; // 遍历员工的进出顺序 for (int info : seatOrLeave) { // 如果当前元素值为负数表示出场特殊位置 0 的员工不会离开 // 例如 -4 表示坐在位置 4 的员工离开保证有员工坐在该座位上 if (info 0) { int leaveIdx -info; seatIdx.remove(new Integer(leaveIdx)); continue; } // 如果当前元素值为 1表示进场 // 如果没有空闲位置则坐不下 if (seatIdx.size() seatNum) { // 假设当前人就是最后一个人 lastSeatIdx -1; continue; } if (seatIdx.size() 0) { // 当前人员进场前座位上没有人则当前人员是第一个进场的直接坐第0个位置 seatIdx.add(0); lastSeatIdx 0; } else if (seatIdx.size() 1) { // 当前人员进场前座位上只有一个人那么这个人肯定坐在第0个位置则当前进场的人坐在 seatNum - 1 位置才能离 0 位置最远 seatIdx.add(seatNum - 1); lastSeatIdx seatNum - 1; } else { // 记录具有最大社交距离的座位号 int bestSeatIdx -1; // 记录最大社交距离 int bestSeatDis -1; // 找到连续空闲座位区域该区域左、右边界是坐了人的座位 int left seatIdx.get(0); // 左边界 for (int i 1; i seatIdx.size(); i) { int right seatIdx.get(i); // 右边界 // 连续空闲座位区域的长度 int dis right - left - 1; // 如果连续空闲座位区域长度为0则无法坐人此时遍历下一个连续空闲座位区域 // 如果连续空闲座位区域长度大于0则可以坐人 if (dis 0) { // 当前空闲区域能产生的最大社交距离 int curSeatDis dis / 2 - (dis % 2 0 ? 1 : 0); // 当前空闲区域中具备最大社交距离的位置 int curSeatIdx left curSeatDis 1; // 保留最优解 if (curSeatDis bestSeatDis) { bestSeatDis curSeatDis; bestSeatIdx curSeatIdx; } } left right; } // 如果最后一个座位即第 seatNum - 1 号座位没有坐人的话比如 1 0 0 0 1 0 0 0 0此时最后一段空闲区域是没有右边界的需要特殊处理 if (seatIdx.get(seatIdx.size() - 1) seatNum - 1) { // 此时可以直接坐到第 seatNum - 1 号座位最大社交距离为 curSeatDis int curSeatDis seatNum - 1 - seatIdx.get(seatIdx.size() - 1) - 1; int curSeatIdx seatNum - 1; // 保留最优解 if (curSeatDis bestSeatDis) { bestSeatIdx curSeatIdx; } } // 如果能坐人则将坐的位置加入seatIdx中 if (bestSeatIdx 0) { seatIdx.add(bestSeatIdx); seatIdx.sort((a, b) - a - b); } // 假设当前人就是最后一个人那么无论当前人是否能坐进去都更新lastSeatIdx bestSeatIdx lastSeatIdx bestSeatIdx; } } return lastSeatIdx; } }Python算法源码# 输入获取 seatNum int(input()) seatOrLeave eval(input()) # 算法入口 def getResult(): # 记录已经坐人位置的序号 seatIdx [] # 记录题解 lastSeatIdx -1 # 遍历员工的进出顺序 for info in seatOrLeave: # 如果当前元素值为负数表示出场特殊位置 0 的员工不会离开 # 例如 -4 表示坐在位置 4 的员工离开保证有员工坐在该座位上 if info 0: leaveIdx -info seatIdx.remove(leaveIdx) continue # 如果当前元素值为 1表示进场 # 如果没有空闲位置则坐不下 if len(seatIdx) seatNum: lastSeatIdx -1 continue if len(seatIdx) 0: # 当前人员进场前座位上没有人则当前人员是第一个进场的直接坐第0个位置 seatIdx.append(0) lastSeatIdx 0 elif len(seatIdx) 1: # 当前人员进场前座位上只有一个人那么这个人肯定坐在第0个位置则当前进场的人坐在 seatNum - 1 位置才能离 0 位置最远 seatIdx.append(seatNum - 1) lastSeatIdx seatNum - 1 else: # 记录具有最大社交距离的座位号 bestSeatIdx -1 # 记录最大社交距离 bestSeatDis -1 # 找到连续空闲座位区域该区域左、右边界是坐了人的座位 left seatIdx[0] # 左边界 for i in range(1, len(seatIdx)): right seatIdx[i] # 右边界 # 连续空闲座位区域的长度 dis right - left - 1 # 如果连续空闲座位区域长度为0则无法坐人此时遍历下一个连续空闲座位区域 # 如果连续空闲座位区域长度大于0则可以坐人 if dis 0: # 当前空闲区域能产生的最大社交距离 curSeatDis dis // 2 - (1 if dis % 2 0 else 0) # 当前空闲区域中具备最大社交距离的位置 curSeatIdx left curSeatDis 1 # 保留最优解 if curSeatDis bestSeatDis: bestSeatDis curSeatDis bestSeatIdx curSeatIdx left right # 如果最后一个座位即第 seatNum - 1 号座位没有坐人的话比如 1 0 0 0 1 0 0 0 0此时最后一段空闲区域是没有右边界的需要特殊处理 if seatIdx[-1] seatNum - 1: # 此时可以直接坐到第 seatNum - 1 号座位最大社交距离为 curSeatDis curSeatDis seatNum - 1 - seatIdx[-1] - 1 curSeatIdx seatNum - 1 # 保留最优解 if curSeatDis bestSeatDis: bestSeatIdx curSeatIdx # 如果能坐人则将坐的位置加入seatIdx中 if bestSeatIdx 0: seatIdx.append(bestSeatIdx) seatIdx.sort() # 假设当前人就是最后一个人那么无论当前人是否能坐进去都更新lastSeatIdx bestSeatIdx lastSeatIdx bestSeatIdx return lastSeatIdx # 算法调用 print(getResult())C算法源码#include stdio.h #include stdlib.h #define MAX_SIZE 500 int cmp(const void *a, const void *b) { return *((int *) a) - *((int *) b); } int main() { int seatNum; scanf(%d, seatNum); getchar(); int seatOrLeave[MAX_SIZE] {0}; int seatOrLeave_size 0; while (scanf([%d, seatOrLeave[seatOrLeave_size]) || scanf(%d, seatOrLeave[seatOrLeave_size])) { seatOrLeave_size; if (getchar() ! ,) break; } // 记录已经坐人位置的序号 int seatIdx[MAX_SIZE]; int seatIdx_size 0; // 记录题解 int lastSeatIdx -1; // 遍历员工的进出顺序 for (int i 0; i seatOrLeave_size; i) { int info seatOrLeave[i]; // 如果当前元素值为负数表示出场特殊位置 0 的员工不会离开 // 例如 -4 表示坐在位置 4 的员工离开保证有员工坐在该座位上 if (info 0) { int leaveIdx -info; // 删除seatIdx中对应leaveIdx int j 0; for (; j seatIdx_size; j) { if (seatIdx[j] leaveIdx) break; } for (; j seatIdx_size - 1; j) { seatIdx[j] seatIdx[j 1]; } seatIdx_size--; continue; } // 如果当前元素值为 1表示进场 // 如果没有空闲位置则坐不下 if(seatIdx_size seatNum) { // 假设当前人就是最后一个人 lastSeatIdx -1; continue; } if (seatIdx_size 0) { // 当前人员进场前座位上没有人则当前人员是第一个进场的直接坐第0个位置 seatIdx[seatIdx_size] 0; lastSeatIdx 0; } else if (seatIdx_size 1) { // 当前人员进场前座位上只有一个人那么这个人肯定坐在第0个位置则当前进场的人坐在 seatNum - 1 位置才能离 0 位置最远 seatIdx[seatIdx_size] seatNum - 1; lastSeatIdx seatNum - 1; } else { // 记录具有最大社交距离的座位号 int bestSeatIdx -1; // 记录最大社交距离 int bestSeatDis -1; // 找到连续空闲座位区域该区域左、右边界是坐了人的座位 int left seatIdx[0]; // 左边界 for (int j 1; j seatIdx_size; j) { int right seatIdx[j]; // 右边界 // 连续空闲座位区域的长度 int dis right - left - 1; // 如果连续空闲座位区域长度为0则无法坐人此时遍历下一个连续空闲座位区域 // 如果连续空闲座位区域长度大于0则可以坐人 if (dis 0) { // 当前空闲区域能产生的最大社交距离 int curSeatDis dis / 2 - (dis % 2 0 ? 1 : 0); // 当前空闲区域中具备最大社交距离的位置 int curSeatIdx left curSeatDis 1; // 保留最优解 if (curSeatDis bestSeatDis) { bestSeatDis curSeatDis; bestSeatIdx curSeatIdx; } } left right; } // 如果最后一个座位即第 seatNum - 1 号座位没有坐人的话比如 1 0 0 0 1 0 0 0 0此时最后一段空闲区域是没有右 if (seatIdx[seatIdx_size - 1] seatNum - 1) { // 此时可以直接坐到第 seatNum - 1 号座位最大社交距离为 curSeatDis int curSeatDis seatNum - 1 - seatIdx[seatIdx_size - 1] - 1; int curSeatIdx seatNum - 1; // 保留最优解 if (curSeatDis bestSeatDis) { bestSeatIdx curSeatIdx; } } // 如果能坐人则将坐的位置加入seatIdx中 if (bestSeatIdx 0) { seatIdx[seatIdx_size] bestSeatIdx; qsort(seatIdx, seatIdx_size, sizeof(int), cmp); } // 假设当前人就是最后一个人那么无论当前人是否能坐进去都更新lastSeatIdx bestSeatIdx lastSeatIdx bestSeatIdx; } } printf(%d\n, lastSeatIdx); return 0; }