#P3258. 最大社交距离(200分)
-
1000ms
Tried: 26
Accepted: 0
Difficulty: 5
所属公司 :
华为od
最大社交距离(200分)
No testdata at current.
思路:模拟
首先,按顺序考虑数组中的每一个值w[i],同时维护一个数组person按从小到大的顺序存储已经就座的这些员工的编号。
- w[i]<0,我们需要在person数组中找到与w[i]相等的数,并删除
- w[i]=0,根据题目说明,不予处理
- w[i]>0,需要分以下几种情况讨论
情况1:person长度为0,说明没有人落座,那么按照题目要求,应该落座在索引0的位置上
情况2:person长度为1,说明只有一个人落座,根据情况1可知,这个人一定在索引0的位置上,因此当前这个人应该落座在索引位置为setNum−1的位置上
情况3:person长度≥2,那么我们应该枚举所有的空位,根据题意去求一个位置,使得这个位置到其他落座的人的最小值最大,那么由于person是一个有序数组,因此可以把整个座位分成k份,k为person的长度,比如person=[0,4,9],那么就可以把区间分为[0,4],[4,9]这两份,特殊的,其实还是需要考虑[9,9]这个区间,但因为这个区间没办法落座,因此不需要考虑
比如对于区间[a,b],那么最优解一定是选择区间[a,b]的中间位置pos,我们计算其距离最大值为ceil(2b−a−1),ceil()表示上取整,例如[0,9]区间,距离最大值为ceil(29−0−1)=4,一边枚举一边更新即可,最后将对应的位置pos插入之后,需要对person数组进行重新排序。
JavaScript
// 引入readline模块
const readline = require('readline');
// 创建readline接口
const rl = readline.createInterface({
input: process.stdin, // 从标准输入读取数据
output: process.stdout // 输出到标准输出
});
let setNum; // 座位总数
let w; // 事件序列
// 读取第一行输入
rl.once('line', (input) => {
setNum = parseInt(input);
// 读取第二行输入
rl.once('line', (input) => {
// 处理第二行输入,提取座位事件序列
w = input.slice(1, -1).split(',').map(Number);
const person = []; // 已经就座的座位编号
let ans = -1; // 输出结果
// 遍历座位事件序列
for (const x of w) {
if (x < 0) { // 如果为负数,表示有人要离场
const pos = -x; // 离场的座位编号
const idx = person.indexOf(pos); // 查找座位在已就座序列中的下标
if (idx !== -1) {
person.splice(idx, 1); // 从已就座序列中移除该座位
}
} else if (x === 0) {
continue; // 如果为零,表示无事件,继续下一次循环
} else if (person.length === 0) {
person.push(0); // 如果座位没有坐人,第一个人坐在最左边
ans = 0; // 更新输出结果
} else if (person.length === 1) {
person.push(setNum - 1); // 如果座位上只有一个人,第二个人坐在最右边
ans = setNum - 1; // 更新输出结果
} else {
let pos = -1; // 新来的人坐的位置
let maxdist = 0; // 最大距离
for (let i = 1; i < person.length; i++) {
if (person[i] - person[i - 1] === 1) { // 两个人之间没空位
continue;
}
const dist = Math.floor((person[i] - person[i - 1]) / 2);
if (dist > maxdist) { // 相同区间取最小下标,因此=不需要更新
maxdist = dist;
pos = person[i - 1] + maxdist;
}
}
if (setNum - 1 - person[person.length - 1] > maxdist) { // 最后一个人的位置是否能坐人
maxdist = setNum - 1 - person[person.length - 1];
pos = person[person.length - 1] + maxdist;
}
if (pos !== -1) {
person.push(pos);
ans = pos;
person.sort((a, b) => a - b);
}
}
}
console.log(ans); // 输出结果
rl.close(); // 关闭readline接口
});
});
Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int setNum = scanner.nextInt();
scanner.nextLine(); // consume the newline character
String s = scanner.nextLine();
List<Integer> w = new ArrayList<>();
StringBuilder t = new StringBuilder();
for (int i = 1; i < s.length() - 1; i++) {
if (s.charAt(i) == ',') {
int num = Integer.parseInt(t.toString());
w.add(num);
t.setLength(0);
} else {
t.append(s.charAt(i));
}
}
w.add(Integer.parseInt(t.toString()));
List<Integer> person = new ArrayList<>(); // 已经就座的座位编号
int ans = -1;
for (int x : w) {
if (x < 0) { // 说明有人要离场
int pos = -x;
if (person.contains(pos)) {
person.remove(Integer.valueOf(pos));
}
} else if (x == 0) {
continue;
} else if (person.isEmpty()) { // 座位没有坐人
person.add(0);
ans = 0;
} else if (person.size() == 1) { // 座位上只有一个人,那么第二个人一定是坐最右边
person.add(setNum - 1);
ans = setNum - 1;
} else {
int pos = -1; // 新来的人坐的位置
int maxDist = 0; // 最大距离
for (int i = 1; i < person.size(); i++) { // 枚举每两个人之间的空位
if (person.get(i) - person.get(i - 1) == 1) { // 两个人之间没空位
continue;
}
int dist = (person.get(i) - person.get(i - 1)) / 2;
if (dist > maxDist) { // 相同区间取最小下标,因此=不需要更新
maxDist = dist;
pos = person.get(i - 1) + maxDist;
}
}
if (setNum - 1 - person.get(person.size() - 1) > maxDist) { // 最后一个人的位置是否能坐人
maxDist = setNum - 1 - person.get(person.size() - 1);
pos = person.get(person.size() - 1) + maxDist;
}
if (pos != -1) {
person.add(pos);
ans = pos;
Collections.sort(person);
}
}
}
System.out.println(ans);
}
}
Python
setNum=int(input())
w=list(map(int,input()[1:-1].split(',')))
person=[] #已经就座的座位编号
ans=-1
for x in w:
if x<0: #说明有人要离场
pos=-x
if pos in person:
idx=person.index(pos) #找到对应编号
person.pop(idx)
elif x==0:
continue
elif len(person)==0: #座位没有坐人
person.append(0)
ans=0
elif len(person)==1: #座位上只有一个人,那么第二个人一定是坐最右边
person.append(setNum-1)
ans=setNum-1
else:
pos=-1 #新来的人坐的位置
maxdist=0 #最大距离
for i in range(1,len(person)): #枚举每两个人之间的空位
if person[i]-person[i-1]==1: #两个人之间没空位
continue
dist=(person[i]-person[i-1])//2
if dist>maxdist: #相同区间取最小下标,因此=不需要更新
maxdist=dist
pos=person[i-1]+maxdist
if setNum-1-person[-1]>maxdist: #最后一个人的位置是否能坐人
maxdist=setNum-1-person
pos=person[-1]+maxdist
if pos!=-1:
person.append(pos)
ans=pos
person.sort()
print(ans)
C++
#include<bits/stdc++.h>
using namespace std;
int main() {
int setNum;
cin >> setNum;
vector<int> w;
string s,t;
cin>>s;
for(int i=1;i<s.size()-1;i++){
if(s[i]==','){
int num=stoi(t,nullptr,10);
w.push_back(num);
t.clear();
}
else{
t.push_back(s[i]);
}
}
w.push_back(stoi(t,nullptr,10));
vector<int> person; // 已经就座的座位编号
int ans = -1;
for (int x : w) {
if (x < 0) { // 说明有人要离场
int pos = -x;
auto it = find(person.begin(), person.end(), pos);
if (it != person.end()) {
person.erase(it);
}
} else if (x == 0) {
continue;
} else if (person.empty()) { // 座位没有坐人
person.push_back(0);
ans = 0;
} else if (person.size() == 1) { // 座位上只有一个人,那么第二个人一定是坐最右边
person.push_back(setNum - 1);
ans = setNum - 1;
} else {
int pos = -1; // 新来的人坐的位置
int maxDist = 0; // 最大距离
for (int i = 1; i < person.size(); i++) { // 枚举每两个人之间的空位
if (person[i] - person[i - 1] == 1) { // 两个人之间没空位
continue;
}
int dist = (person[i] - person[i - 1]) / 2;
if (dist > maxDist) { // 相同区间取最小下标,因此=不需要更新
maxDist = dist;
pos = person[i - 1] + maxDist;
}
}
if (setNum - 1 - person.back() > maxDist) { // 最后一个人的位置是否能坐人
maxDist = setNum - 1 - person.back();
pos = person.back() + maxDist;
}
if (pos != -1) {
person.push_back(pos);
ans = pos;
sort(person.begin(), person.end());
}
}
}
cout<<ans<<endl;
return 0;
}
题目描述
疫情期间需要大家保持一定的社交距离,公司组织开交流会议。
座位一排共 N 个座位,编号分别为[0,N−1]。
要求员工一个接着一个进入会议室,并且可以在任何时候离开会议室。
满足:
每当一个员工进入时,需要坐到最大社交距离(最大化自己和其他人的距离的座位);
如果有多个这样的座位,则坐到索引最小的那个座位。
输入描述
会议座位总数 seatNum。1≤seatNum≤500.
员工的进出顺序 seatOrLeave 数组 。
元素值为 1 ,表示进场
元素值为负数,表示出场(特殊:位置 0 的员工不会离开)
例如 −4 表示坐在位置 4 的员工离开(保证所有员工坐在该座位上)
输出描述
最后进来的员工,他会坐在第几个位置,如果位置已满,则输出 −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 号座位上