1 条题解
-
0
解决思路
为了高效实现团队队列,我们需要满足以下操作的时间复杂度要求:
- ENQUEUE x:O(1) 时间找到 x 所属团队的末尾位置并插入。
- DEQUEUE:O(1) 时间移除队首元素。
数据结构选择
- 团队标识映射:使用哈希表(如
unordered_map
)记录每个元素所属的团队编号,以便快速查找。 - 队列结构:
- 主队列:保存团队的顺序。每个团队在第一次出现时加入主队列。
- 团队内部队列:每个团队维护一个队列,保存该团队的元素顺序。
具体实现
- 主队列:是一个队列,保存当前有元素在团队队列中的团队编号。
- 团队队列数组:一个数组或哈希表,每个团队对应一个队列,保存该团队的元素。
操作细节:
- ENQUEUE x:
- 查找 x 的团队编号 t。
- 如果团队 t 的队列为空,将 t 加入主队列。
- 将 x 加入团队 t 的队列。
- DEQUEUE:
- 从主队列的队首获取团队编号 t。
- 从团队 t 的队列中取出队首元素并输出。
- 如果团队 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
- 上传者