1 条题解

  • 0
    @ 2025-5-6 20:48:57

    解决思路

    为了高效实现团队队列,我们需要满足以下操作的时间复杂度要求:

    • ENQUEUE x:O(1) 时间找到 x 所属团队的末尾位置并插入。
    • DEQUEUE:O(1) 时间移除队首元素。

    数据结构选择

    1. 团队标识映射:使用哈希表(如 unordered_map)记录每个元素所属的团队编号,以便快速查找。
    2. 队列结构
      • 主队列:保存团队的顺序。每个团队在第一次出现时加入主队列。
      • 团队内部队列:每个团队维护一个队列,保存该团队的元素顺序。

    具体实现

    • 主队列:是一个队列,保存当前有元素在团队队列中的团队编号。
    • 团队队列数组:一个数组或哈希表,每个团队对应一个队列,保存该团队的元素。

    操作细节

    • ENQUEUE x
      1. 查找 x 的团队编号 t。
      2. 如果团队 t 的队列为空,将 t 加入主队列。
      3. 将 x 加入团队 t 的队列。
    • DEQUEUE
      1. 从主队列的队首获取团队编号 t。
      2. 从团队 t 的队列中取出队首元素并输出。
      3. 如果团队 t 的队列为空,将 t 从主队列中移除。

    解决代码

    #include <iostream>
    #include <queue>
    #include <vector>
    #include <string>
    using namespace std;
    
    const int MAX_ELEMENT = 1000000;
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(NULL);  // Changed from nullptr to NULL
        
        int t, scenario = 1;
        while (cin >> t && t != 0) {
            cout << "Scenario #" << scenario++ << "\n";
            
            vector<int> elementToTeam(MAX_ELEMENT, -1);
            for (int teamId = 0; teamId < t; ++teamId) {
                int n;
                cin >> n;
                for (int j = 0; j < n; ++j) {
                    int element;
                    cin >> element;
                    elementToTeam[element] = teamId;
                }
            }
            
            queue<int> teamQueue;
            vector<queue<int> > teamElements(t);  // Added space between > >
            vector<bool> isTeamInQueue(t, false);
            
            string command;
            while (cin >> command) {
                if (command == "STOP") {
                    break;
                } else if (command == "ENQUEUE") {
                    int x;
                    cin >> x;
                    int team = elementToTeam[x];
                    if (!isTeamInQueue[team]) {
                        teamQueue.push(team);
                        isTeamInQueue[team] = true;
                    }
                    teamElements[team].push(x);
                } else if (command == "DEQUEUE") {
                    int frontTeam = teamQueue.front();
                    cout << teamElements[frontTeam].front() << "\n";
                    teamElements[frontTeam].pop();
                    if (teamElements[frontTeam].empty()) {
                        teamQueue.pop();
                        isTeamInQueue[frontTeam] = false;
                    }
                }
            }
            cout << "\n";
        }
        return 0;
    }
    
    • 1

    信息

    ID
    1259
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    5
    已通过
    1
    上传者