首页 > 试题广场 >

公司食堂

[编程题]公司食堂

热度指数：23936 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美和小团所在公司的食堂有N张餐桌，从左到右摆成一排，每张餐桌有2张餐椅供至多2人用餐，公司职员排队进入食堂用餐。小美发现职员用餐的一个规律并告诉小团：当男职员进入食堂时，他会优先选择已经坐有1人的餐桌用餐，只有当每张餐桌要么空着要么坐满2人时，他才会考虑空着的餐桌；

当女职员进入食堂时，她会优先选择未坐人的餐桌用餐，只有当每张餐桌都坐有至少1人时，她才会考虑已经坐有1人的餐桌；

无论男女，当有多张餐桌供职员选择时，他会选择最靠左的餐桌用餐。现在食堂内已有若干人在用餐，另外M个人正排队进入食堂，小团会根据小美告诉他的规律预测排队的每个人分别会坐哪张餐桌。

进阶：时间复杂度 $O(nlogn)\$ ,空间复杂度 $O(n)\$

输入描述:

第一行输入一个整数T（1<=T<=10），表示数据组数。

每组数据占四行，第一行输入一个整数N（1<=N<=500000）；

第二行输入一个长度为N且仅包含数字0、1、2的字符串，第i个数字表示左起第i张餐桌已坐有的用餐人数；

第三行输入一个整数M（1<=M<=2N且保证排队的每个人进入食堂时都有可供选择的餐桌）；

第四行输入一个长度为M且仅包含字母M、F的字符串，若第i个字母为M，则排在第i的人为男性，否则其为女性。

输出描述:

每组数据输出占M行，第i行输出一个整数j（1<=j<=N），表示排在第i的人将选择左起第j张餐桌用餐。

示例1

输入

1
5
01102
6
MFMMFF

输出

算法知识视频讲解

JavaScript

牛客538022010号

js v8 来了

思路与其他同学大致相同，只不过在js中要手动实现小根堆，前端同学太难

注意以下几点可以节省运行时间：

1、尽量只使用一个堆，存放坐0人的桌子用数组就好

2、不要使用 shift 方法，该方法时间复杂度较高（n或logn），对0人的桌子设置索引，每次占用则索引+1，这样需要坐0人的桌子时只需访问该数组中该索引的元素

class PriorityQueue {
    constructor() {
        this.tree = [];
    }

    insert(val) {
        this.tree.push(val);
        this._up(this.tree.length - 1);
    }

    remove() {
        let last = this.tree.pop();
        if (this.tree.length > 0) {
            this.tree[0] = last;
            this._down(0);
        }
    }

    _down(index) {
        let tree = this.tree;
        let last_no_leaf = ~~((tree.length - 2) / 2);
        if (index > last_no_leaf) return;
        while (index <= last_no_leaf) {
            let l = tree[index * 2 + 1];
            let r = tree[index * 2 + 2] || tree[index * 2 + 1];
            let min = l <= r ? l : r;
            let minIndex = l <= r ? index * 2 + 1 : index * 2 + 2
            if (tree[index] > min) {
                [tree[index], tree[minIndex]] = [tree[minIndex], tree[index]]
                index = minIndex
            } else {
                return;
            }
        }
    }

    _up(index) {
        let tree = this.tree;
        while (index !== 0) {
            let p = ~~((index - 1) / 2);
            if (tree[index] < tree[p]) {
                [tree[index], tree[p]] = [tree[p], tree[index]];
                index = p;
            } else {
                return;
            }
        }
    }
}

readline();
let result = '';
while(line = readline()){
    const n = ~~line;
    let ts = readline().split('');
    const m = ~~readline(),
          ga = readline();

    let t0 = [],t1 = new PriorityQueue();
    ts.forEach((e,i)=>{
        if(e=='0'){
            t0.push(i+1);
        }else if(e=='1'){
            t1.tree.push(i+1);
        }
    })

    let index0 = 0;
    for(let i =0;i<m;i++){
        if((ga[i]=='M'&&t1.tree.length>0)||(ga[i]=='F'&&index0>=t0.length)){
            result+=t1.tree[0]+'\n';
            t1.remove();
        }else{
            result+=t0[index0]+'\n';
            t1.insert(t0[index0]);
            index0++;
        }
    }
}
console.log(result);

发表于 2021-11-19 12:41:40 回复(1)