【队列栈】 51nod1289. 大鱼吃小鱼

怼烎@ 2022-12-02 15:24 121阅读 0赞

### 题目 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center 1]

### 解答 ###

#include <iostream>
    #include <string>
    #include <list>
    #include <vector>
    #include <stack>
    
    int main() { 
      int n = 0;
      std::cin >> n;
    
      int size = 0;
      int dir = 0;
    
      std::stack<int> num_stack;
      int total = n;
    
      while (n != 0) { 
        --n;
    
        std::cin >> size;
        std::cin >> dir;
    
        // 向右入栈
        if (dir > 0) { 
          num_stack.push(size);
          continue;
        }
    
        // 向左则与栈顶元素比较，比栈顶元素大，则不断吃掉栈顶元素的鱼，否则自己被吃掉。
        while (!num_stack.empty()) { 
          if (size > num_stack.top()) { 
            num_stack.pop();
            total--;
          } else { 
            total--;
            break;
          }
        }
      }
    
      std::cout << total;
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200831223116493.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/dcbf846c67ea4c0eb10315741c783939.png