推荐|【华为OD-E卷 -62 模拟消息队列 100分（python、java、c++、js、c）】

【华为OD-E卷 - 模拟消息队列 100分（python、java、c++、js、c）】

题目

让我们来模拟一个消息队列的运作，有一个发布者和若干消费者，发布者会在给定的时刻向消息队列发送消息，
若此时消息队列有消费者订阅，这个消息会被发送到订阅的消费者中优先级最高（输入中消费者按优先级升序排列）的一个；若此时没有订阅的消费者，该消息被消息队列丢弃。消费者则会在给定的时刻订阅消息队列或取消订阅。
当消息发送和订阅发生在同一时刻时，先处理订阅操作，即同一时刻订阅的消费者成为消息发送的候选。当消息发送和取消订阅发生在同一时刻时，先处理取消订阅操作，即消息不会被发送到同一时刻取消订阅的消费者。

输入描述

输入为两行。

第一行为2N个正整数，代表发布者发送的N个消息的时刻和内容（为方便解折，消息内容也用正整数表示）。第一个数字是第一个消息的发送时刻，第二个数字是第一个消息的内容，以此类推。用例保证发送时刻不会重复，但注意消息并没有按照发送时刻排列。

第二行为2M个正整数，代表M个消费者订阅和取消订阅的时刻。第一个数字是第一个消费者订阅的时刻，第二个数字是第一个消费者取消订阅的时刻，以此类推。用例保证每个消费者的取消订阅时刻大于订阅时刻，消费者按优先级升序排列。

两行的数字都由空格分隔。N不超过100，M不超过10，每行的长度不超过1000字符

输出描述

输出为M行，依次为M个消费者收到的消息内容，消息内容按收到的顺序排列，且由空格分隔；

若某个消费者没有收到任何消息，则对应的行输出-1

用例

用例一：

输入：

2 22 1 11 4 44 5 55 3 33
1 7 2 3

输出：

11 33 44 55
22

说明消息11在1时刻到达，此时只有第一个消费者订阅，消息发送给它；

消息22在2时刻到达，此时两个消费者都订阅了，消息发送给优先级最高的第二个消费者；

消息33在时刻3到达，此时只有第一个消费者订阅，消息发送给它；

余下的消息按规则也是发送给第一个消费者

用例二：

输入：

5 64 11 64 9 97
9 11 4 9

输出：

97
64

说明消息64在5时刻到达，此时只有第二个消费者订阅，消息发送给它；

消息97在9时刻到达，此时只有第一消费者订阅(因为第二个消费者刚好在9时刻取消订阅)，消息发送给它;

11时刻也到达了一个内容为64的消息，不过因为没有消费者订阅，消息被丢弃

python解法

解题思路：
解题思路
本题的目的是模拟消息的传递，给定两个数组，一个表示发布者发布消息的时间及内容，另一个表示订阅者的订阅时间和退订时间。我们需要根据每个发布者发布消息的时间和每个订阅者的订阅时间以及退订时间，判断订阅者能接收到哪些消息。

解决步骤：
输入解析：

pubArr 数组包含一对一对的发布者发布消息的时间和消息内容，依次组成 (publish_time, content)。
subArr 数组包含一对一对的订阅者的订阅时间和退订时间，依次组成 (sub_time, unsub_time)。
处理发布者与订阅者信息：

将发布者的时间与消息内容组合成一个元组，并按发布的时间排序，确保我们按时间顺序处理消息。
将订阅者的订阅时间和退订时间组合成一个元组。
创建一个 subscriber_content 列表，用于存储每个订阅者所接收到的消息内容。
模拟消息的传递：

遍历所有发布者，对于每个发布者，在其发布消息时，查看每个订阅者是否在有效的订阅期内（即订阅时间小于等于发布者的发布消息时间且退订时间大于等于发布消息时间）。
如果订阅者在有效订阅期内，则该订阅者接收到该消息，并把消息内容添加到该订阅者的消息列表中。
输出结果：

对每个订阅者，输出其接收到的所有消息。如果某个订阅者没有接收到任何消息，则输出 -1。

from collections import deque

# 处理发布者和订阅者消息的函数
def process_messages(pubArr, subArr):
    # 将发布者的发布信息转换成 (时间, 内容) 元组并存储
    publishers = []
    for i in range(0, len(pubArr), 2):
        publishers.append((pubArr[i], pubArr[i + 1]))

    # 将订阅者的订阅信息转换成 (订阅时间, 退订时间) 元组并存储
    subscribers = []
    for i in range(0, len(subArr), 2):
        subscribers.append((subArr[i], subArr[i + 1]))

    # 按发布者的发布消息时间升序排序
    publishers.sort(key=lambda x: x[0])

    # 初始化一个二维列表，用于存储每个订阅者接收到的消息内容
    subscriber_content = [[] for _ in range(len(subscribers))]

    # 遍历所有的发布者信息
    for pub_time, pub_content in publishers:
        # 反向遍历订阅者，检查订阅者是否处于有效订阅期内
        for j in range(len(subscribers)-1, -1, -1):
            sub_time, unsub_time = subscribers[j]
            # 如果发布者的发布消息时间在订阅者的订阅期内，添加消息内容
            if unsub_time > pub_time >= sub_time:
                subscriber_content[j].append(pub_content)
                break  # 找到一个有效的订阅者后就停止，避免重复分配消息

    # 输出每个订阅者接收到的消息内容
    for contents in subscriber_content:
        # 如果订阅者接收到的消息为空，输出 "-1"，否则输出消息内容
        print(" ".join(map(str, contents)) if contents else "-1")

# 输入数据：发布者发布的消息时间和内容，以及订阅者的订阅和退订时间
pubArr = list(map(int, input().split()))
subArr = list(map(int, input().split()))

# 调用处理函数
process_messages(pubArr, subArr)

java解法

解题思路
解题思路
本题的核心任务是模拟消息发布者和订阅者之间的消息传递。给定两组数组，分别表示发布者的消息时间和内容，订阅者的订阅时间和退订时间。我们需要根据每个发布者发布消息的时间和每个订阅者的订阅和退订时间，判断每个订阅者能够接收到哪些消息。

解决步骤：
输入数据：

msgArr：包含发布者的消息时间和内容，每两个数表示一个发布者发布消息的时间和消息内容。
consArr：包含订阅者的订阅时间和退订时间，每两个数表示一个订阅者的订阅时间和退订时间。
整理数据：

将 msgArr 按照每对时间和内容整理成二维数组 msgs，每个元素是一个长度为2的数组，存储消息的时间和内容。
将 consArr 按照每对订阅时间和退订时间整理成二维数组 consumers，每个元素是一个长度为2的数组，存储订阅时间和退订时间。
消息排序：

将消息按时间升序排列，这样可以确保我们按照发布顺序处理消息。
模拟消息传递：

对于每个消息，检查所有订阅者的有效订阅期（订阅时间小于等于消息时间且退订时间大于等于消息时间）。如果符合条件，订阅者接收到该消息，记录该消息。
输出结果：

对每个订阅者，输出其接收到的消息内容。如果订阅者没有接收到任何消息，输出 -1

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取并解析消息发布者的数据
        int[] msgArr = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 读取并解析订阅者的数据
        int[] consArr = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        // 调用处理消息的函数
        processMessages(msgArr, consArr);
    }

    // 处理消息发布和订阅的函数
    public static void processMessages(int[] msgArr, int[] consArr) {
        int msgLen = msgArr.length;  // 消息发布者数组的长度
        int consLen = consArr.length;  // 订阅者数组的长度

        // 将消息发布者的数据按时间和内容分组，存储为二维数组
        int[][] msgs = new int[msgLen / 2][];
        int i = 0;
        int mIdx = 0;
        while (i < msgLen) {
            msgs[mIdx++] = new int[] {msgArr[i], msgArr[i + 1]};  // 每个发布者的时间和内容
            i += 2;  // 步进2个元素
        }

        // 将订阅者的数据按订阅时间和退订时间分组，存储为二维数组
        int[][] consumers = new int[consLen / 2][];
        int j = 0;
        int cIdx = 0;
        while (j < consLen) {
            consumers[cIdx++] = new int[] {consArr[j], consArr[j + 1]};  // 每个订阅者的订阅时间和退订时间
            j += 2;  // 步进2个元素
        }

        // 按发布的时间对消息进行升序排序
        Arrays.sort(msgs, (x, y) -> x[0] - y[0]);

        // 创建一个 ArrayList 用于存储每个订阅者接收到的消息
        ArrayList<ArrayList<Integer>> receivedMsgs = new ArrayList<>();
        for (int k = 0; k < consumers.length; k++) {
            receivedMsgs.add(new ArrayList<>());  // 每个订阅者的消息列表
        }

        // 遍历所有发布的消息
        int pubIdx = 0;
        while (pubIdx < msgs.length) {
            int msgTime = msgs[pubIdx][0];  // 获取当前消息的发布时间
            int msgContent = msgs[pubIdx][1];  // 获取当前消息的内容

            // 遍历所有订阅者（从后往前遍历，优先分配给有效的订阅者）
            int subIdx = consumers.length - 1;
            while (subIdx >= 0) {
                int subTime = consumers[subIdx][0];  // 订阅者的订阅时间
                int unsubTime = consumers[subIdx][1];  // 订阅者的退订时间

                // 如果消息发布时，订阅者处于有效订阅期
                if (msgTime >= subTime && msgTime < unsubTime) {
                    receivedMsgs.get(subIdx).add(msgContent);  // 该订阅者接收到消息
                    break;  // 找到一个有效的订阅者后就停止继续查找
                }
                subIdx--;  // 检查下一个订阅者
            }
            pubIdx++;  // 处理下一个发布的消息
        }

        // 输出每个订阅者接收到的消息内容
        int idx = 0;
        while (idx < receivedMsgs.size()) {
            ArrayList<Integer> contentList = receivedMsgs.get(idx);
            if (contentList.isEmpty()) {
                System.out.println("-1");  // 如果没有接收到任何消息，输出 -1
            } else {
                // 使用 StringJoiner 格式化输出接收到的消息内容
                StringJoiner sj = new StringJoiner(" ");
                for (int content : contentList) {
                    sj.add(Integer.toString(content));  // 添加每条消息
                }
                System.out.println(sj.toString());  // 输出消息内容
            }
            idx++;  // 处理下一个订阅者
        }
    }
}

C++解法

解题思路
解题思路
本题的核心任务是模拟消息队列和订阅者队列的操作，依据每个消息的发送时间和每个订阅者的有效订阅时间判断哪些订阅者能接收到哪些消息。我们将给定的消息和订阅者信息通过排序和检查进行处理，最终输出每个订阅者接收到的消息内容。

解决步骤：
数据解析：

输入包含两行数据：一行表示消息发布者的消息和时间，另一行表示订阅者的订阅和退订时间。我们需要解析这两行数据，并分别存储为 msgArray 和 subArray。
消息和订阅者处理：

将 msgArray 和 subArray 分别处理成 messageQueue 和 subscriptionQueue。每个队列中的元素是一个时间和内容的对（pair），分别代表消息的发送时间和内容，订阅者的订阅时间和退订时间。
排序：

按消息的发送时间对 messageQueue 进行排序，这样可以确保我们按照时间顺序处理消息。
消息分发：

遍历所有消息并检查每个消息是否在某个订阅者的有效订阅时间范围内。如果是，订阅者接收到该消息，并将该消息存储到订阅者对应的接收队列中。
输出结果：

对每个订阅者，输出其接收到的所有消息。如果没有接收到任何消息，输出 -1

#include 
#include 
#include 
#include 
using namespace std;

void processQueue(const vector<int>& msgArray, const vector<int>& subArray) {
    // Step 1: 构建消息队列，将msgArray解析成消息队列
    vector<pair<int, int>> messageQueue;
    for (int i = 0; i < msgArray.size(); i += 2) {
        messageQueue.push_back({ msgArray[i], msgArray[i + 1] });
        // 将每对消息时间和内容作为一对push到消息队列
    }

    // Step 2: 构建订阅者队列，将subArray解析成订阅者队列
    vector<pair<int, int>> subscriptionQueue;
    for (int i = 0; i < subArray.size(); i += 2) {
        subscriptionQueue.push_back({ subArray[i], subArray[i + 1] });
        // 将每对订阅时间和退订时间作为一对push到订阅者队列
    }

    // Step 3: 按消息的发送时间对消息队列进行升序排序
    sort(messageQueue.begin(), messageQueue.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.first < b.first;  // 按时间升序排列
        });

    // Step 4: 为每个订阅者准备一个空的消息接收列表
    vector<vector<int>> receivedMessages(subscriptionQueue.size());

    // Step 5: 遍历消息队列，将消息分配给有效的订阅者
    for (const auto& [sendTime, message] : messageQueue) {
        // 遍历订阅者队列
        for (int i = subscriptionQueue.size() - 1; i >= 0; --i) {
            const auto& [subscribeTime, unsubscribeTime] = subscriptionQueue[i];

            // 如果消息发送时间在订阅者的有效订阅期内
            if (sendTime >= subscribeTime && sendTime < unsubscribeTime) {
                receivedMessages[i].push_back(message);  // 该订阅者接收到消息
                break;  // 一旦找到了合适的订阅者，就停止查找
            }
        }
    }

    // Step 6: 输出每个订阅者接收到的消息
    for (const auto& msgs : receivedMessages) {
        if (msgs.empty()) {
            cout << "-1" << endl;  // 如果该订阅者没有接收到消息，输出-1
        }
        else {
            for (size_t i = 0; i < msgs.size(); ++i) {
                if (i > 0) cout << " ";  // 处理输出格式，消息之间有空格
                cout << msgs[i];  // 输出消息
            }
            cout << endl;  // 输出完一位订阅者的消息后换行
        }
    }
}

int main() {
    string line;
    vector<int> msgArray, subArray;

    // Step 7: 读取并解析消息发布者的数据
    getline(cin, line);  // 读取第一行数据
    stringstream ss1(line);
    int num;
    while (ss1 >> num) {
        msgArray.push_back(num);  // 将消息数据存入msgArray
    }

    // Step 8: 读取并解析订阅者的数据
    getline(cin, line);  // 读取第二行数据
    stringstream ss2(line);
    while (ss2 >> num) {
        subArray.push_back(num);  // 将订阅者数据存入subArray
    }

    // Step 9: 处理消息队列和订阅队列
    processQueue(msgArray, subArray);

    return 0;
}

C解法

解题思路
解题思路
本题目要求模拟消息发布与订阅的过程，关键在于处理消息发布的时间与订阅者的订阅时间对比，从而确定订阅者是否接收某些消息。我们通过以下步骤解决这个问题：

数据输入与解析：

输入的消息与订阅数据分别是两个数组。每个消息由一个时间戳和一个内容组成，订阅者由一个订阅开始时间和一个订阅结束时间组成。
我们首先读取输入数据，将其解析成适当的数据结构。
排序：

将消息按照时间戳升序排序。这样可以确保我们按时间的顺序处理消息，确保消息发送的先后顺序正确。
消息分发：

遍历所有的消息，检查它是否在某个订阅者的有效订阅时间内。如果是，订阅者接收到该消息，并将其添加到订阅者的消息列表中。
输出结果：

对每个订阅者，输出其接收到的所有消息。如果没有接收到任何消息，则输出 -1

#include 
#include 

// 定义消息结构体
typedef struct {
    int time;       // 消息的发送时间
    int content;    // 消息的内容
} Pub;

// 定义订阅者结构体
typedef struct {
    int subTime;    // 订阅开始时间
    int unSubTime;  // 退订时间
    int *messages;  // 存储订阅者接收到的消息
    int count;      // 存储消息的数量
} Sub;

// 排序函数：按照消息的发送时间进行升序排序
int comparePub(const void* a, const void* b) {
    return ((Pub *)a)->time - ((Pub *)b)->time;
}

int main() {
    // 定义存储消息和订阅者信息的数组
    int pubArr[200], subArr[20];
    int pubCount = 0, subCount = 0;

    // 读取消息发布信息
    while (scanf("%d", &pubArr[pubCount]) != EOF) {
        pubCount++;
        if (getchar() == '\n') break;  // 一行输入结束后跳出
    }

    // 读取订阅者信息
    while (scanf("%d", &subArr[subCount]) != EOF) {
        subCount++;
        if (getchar() == '\n') break;  // 一行输入结束后跳出
    }

    // 计算消息和订阅者的数量
    int n = pubCount / 2;  // 消息的数量
    int m = subCount / 2;  // 订阅者的数量
    Pub pubs[n];            // 消息数组
    Sub subs[m];            // 订阅者数组

    // 填充消息数组
    for (int i = 0, j = 0; i < n; i++, j += 2) {
        pubs[i].time = pubArr[j];       // 消息时间
        pubs[i].content = pubArr[j + 1]; // 消息内容
    }

    // 填充订阅者数组
    for (int i = 0, j = 0; i < m; i++, j += 2) {
        subs[i].subTime = subArr[j];    // 订阅开始时间
        subs[i].unSubTime = subArr[j + 1]; // 退订时间
        subs[i].messages = (int *)malloc(n * sizeof(int)); // 为每个订阅者分配消息存储空间
        subs[i].count = 0;  // 初始化接收到的消息数
    }

    // 对消息按照时间进行排序
    qsort(pubs, n, sizeof(Pub), comparePub);

    // 分配消息给订阅者
    for (int i = 0; i < n; i++) {
        int time = pubs[i].time;   // 当前消息的时间
        int content = pubs[i].content;  // 当前消息的内容

        // 遍历所有订阅者
        for (int j = m - 1; j >= 0; j--) {
            // 检查消息是否在订阅者的订阅期内
            if (time >= subs[j].subTime && time < subs[j].unSubTime) {
                subs[j].messages[subs[j].count++] = content;  // 该订阅者接收到消息
                break;  // 一个消息只能被一个订阅者接收，找到合适的订阅者后跳出循环
            }
        }
    }

    // 输出每个订阅者接收到的消息
    for (int i = 0; i < m; i++) {
        if (subs[i].count == 0) {
            // 如果订阅者没有接收到任何消息，输出 -1
            printf("-1\n");
        } else {
            // 如果有消息，输出接收到的所有消息
            for (int j = 0; j < subs[i].count; j++) {
                if (j > 0) printf(" ");  // 处理格式，消息之间用空格隔开
                printf("%d", subs[i].messages[j]);  // 输出消息
            }
            printf("\n");  // 每个订阅者的输出结束后换行
        }
        free(subs[i].messages);  // 释放订阅者消息数组的内存
    }

    return 0;
}

JS解法

解题思路
解题思路
本题目要求模拟消息发布与订阅的过程，其中涉及到两类数据：消息（包括发送时间和内容）与订阅者（包括订阅时间段）。每个订阅者能够接收在其订阅时间范围内发布的消息。通过以下步骤，我们可以解决这个问题：

数据输入：

第一行输入消息数据，每对数据由发送时间和消息内容组成。
第二行输入订阅者数据，每对数据由订阅开始时间和退订时间组成。
排序：

将消息按照时间顺序排序，确保消息按发送时间处理。
消息分发：

对每个消息，检查它是否在某个订阅者的订阅时间范围内。如果在范围内，订阅者接收到该消息。
输出结果：