|
发表于 2023-8-24 13:40:37
|
显示全部楼层
对于你的代码中 'leave' 部分的优化,一种可能的方法是使用一个辅助数据结构来追踪玩家在队列中的位置,以便快速删除。可以使用一个 unordered_map 或 unordered_set 存储玩家名字和相应在队列中的索引。
以下是修改的示例代码:
- #include <iostream>
- #include <deque>
- #include <unordered_set>
- #include <string>
- #include <unordered_map>
- using namespace std;
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0), cout.tie(0);
- int n, p = 0;
- deque<string> q;
- unordered_map<string, int> position; // 玩家名字与索引的映射
- unordered_set<string> s;
- string name, opt, playing[2];
- cin >> n;
- for (int i = 0; i < n; i++) {
- cin >> opt;
- if (opt == "start") {
- for (int i = 0; i < p; i++) {
- q.push_back(playing[ i]);
- q.pop_front(); // 上轮玩家回队尾
- }
- if (q.size() == 0) {
- cout << "Error" << "\n"; // 无人
- } else if (q.size() == 1) { // 一人
- p = 1;
- cout << q.front() << "\n";
- playing[0] = q.front();
- } else {
- p = 2;
- string a = q.front(); // 多人,deque O(1)获取前两名
- q.pop_front();
- cout << a << ' ' << q.front() << "\n";
- playing[0] = a;
- playing[1] = q.front();
- q.push_front(a);
- }
- } else if (opt == "leave") {
- cin >> name;
- int flag = 0;
- if (position.find(name) != position.end()) { // 玩家在队列中
- int index = position[name];
- playing[index] = ""; // 清空该玩家在 playing 数组的位置
- position.erase(name); // 从映射表中删除
- continue;
- }
- if (s.find(name) == s.end()) { // 是否在队中
- cout << "Error" << "\n";
- continue;
- }
- s.erase(name);
- cout << "OK" << "\n";
- for (int i = q.size(); i > 0; i--) {
- if (q.front() == name) {
- q.pop_front(); // O(1)清除
- } else {
- q.push_back(q.front());
- q.pop_front();
- }
- }
- } else if (opt == "arrive") {
- cin >> name;
- if (s.find(name) != s.end()) {
- cout << "Error" << "\n";
- continue;
- }
- s.insert(name); // 加到队尾
- q.push_back(name);
- position[name] = p; // 记录玩家在队列中的位置
- cout << "OK" << "\n";
- }
- }
- return 0;
- }
复制代码
通过使用 unordered_map 在 O(1) 时间复杂度内找到玩家在队列中的位置,并使用 playing 数组记录玩家在队列头部的位置,可以将 'leave' 操作的复杂度优化到 O(1)。这应该会提高代码的效率。
希望这个优化能够帮助你通过测试。如果有任何疑问,请随时询问。祝你好运!
如果问题已经解决,请设置最佳答案 |
|