540 - Team Queue-白红宇

540 - Team Queue

阅读量：6412 次

发布时间：2019-06-23

本文共 2065 字，大约阅读时间需要 6 分钟。

题意:

有组织排队, 即每个人要开始排队时, 先查找是否有与他同组织的人已经在排队, 若是, 则这个可以直接插队到他所在组织的最后; 若找不到组织, 则只能排到队伍的最后. 有 ENQUEUE 与 DEQUEUE 两种命令, ENQUEUE 表示把当前人按前面提到的规则入队, DEQUEUE 表示把队伍最前端的人输出后出队.

思路:

1. 使用 list 来存放各个组织的队伍.

2. 使用 vector 来存放各个 list 的首元素, 主要是为了 DEQUEUE 时能够是从实际队列的头向尾出队的, 即先出队的总是 vector 中排在最前面的 list 的元素; 当此 list 为空后, 就把此 list 从 vector 中删除, 再从下一个 list 中取元素出来进行 DEQUEUE .

3. 每次 ENQUEUE 后, 都要判断此 list 是否已在 vector 中, 若未在, 则说明此人是未找到组织, 新增的一个 list, 需要把其补到 vector 的最后.

要点:

1. list insert 时, 若传进来的 iterator 为 end(), 会直接插在最后面吗? 会的!!!

题目:

代码:

# include 
    
     # include 
     
      # include 
      
       # include 
       
        # include 
        
         # include 
         
          # include 
          
           # include 
           
            # include 
            
             # include 
             
              # include 
              using namespace std;int main(int argc, char const *argv[]){ #ifndef ONLINE_JUDGE freopen("540_i.txt", "r", stdin); freopen("uva_o.txt", "w", stdout); #endif int numScenario = 0; int numTeam; cin >> numTeam; while (numTeam != 0) { cout << "Scenario #" << ++numScenario << endl; map
               
                 elementTeam; // 记录每个 team element 和其对应的队号 map

*> queueHeads; // 记录每个 team 的键表头指针 vector

queueOrder; // 记录从头到尾的各个 queue, 排在前面的在 // DEQUEUE 时会先被 pop_front 出去 // 读入 team 信息 for (int i=0; i

> numElements; for (int j=0; j

> element; elementTeam[element] = i; } list

* queue = new list

(); queueHeads[i] = queue; } // 读入命令, 并执行 string cmd; cin >> cmd; while (cmd != "STOP") { if (cmd == "DEQUEUE") { // 取第一个出来 DEQUEUE int noQueue = queueOrder[0]; list

* queue = queueHeads[noQueue]; // 若 dequeue 后队伍为空, 则从 vector 删掉 cout << *(queue->begin()) << endl; queue->pop_front(); if (queue->empty()) queueOrder.erase(queueOrder.begin()); } else { // cmd == "ENQUEUE" int element; cin >> element; int noQueue = elementTeam[element]; list

* queue = queueHeads[noQueue]; queue->push_back(element); if (find(queueOrder.begin(), queueOrder.end(), noQueue) == queueOrder.end()) { queueOrder.push_back(noQueue); } } cin >> cmd; } cout << endl; cin >> numTeam; } return 0;}

环境: C++ 4.5.3 - GNU C++ Compiler with options: -lm -lcrypt -O2 -pipe -DONLINE_JUDGE

转载于:https://my.oschina.net/zenglingfan/blog/148957

你可能感兴趣的文章