Code+#2 火锅盛宴 - 算法题解与优化 - 常规

Code+#2 火锅盛宴 - 算法题解与优化

题目描述

SkyDec 和 YJQQQAQ 都是 Yazid 的好朋友。他们都非常喜欢吃火锅。有一天，他们聚在一起，享受一场火锅盛宴。这场火锅盛宴中，有一个麻辣浓汤锅底的火锅和 n 种食物，每种食物数量都是无限的。我们用 1 至 n 将这些食材编号。每种食物煮熟所需要的时间不同，第 i 种食物煮熟需要 s_i 单位时间。Yazid 和 YJQQQAQ 的口味不同：YJQQQAQ 觉得所有食物的好吃程度都是相同的；而 Yazid 则觉得没有两种食材的好吃程度是相同的，并且，巧合的是，编号越小的食物 Yazid 越喜欢吃。可怜的 SkyDec 由于不能吃辣，所以只能帮 Yazid 和 YJQQQAQ 煮食物。

整个火锅盛宴持续 10^9 单位时间。在整个盛宴中，三位好朋友除了谈笑风生之外，最重要的事当然就是吃东西了。在任意整数时刻，都有可能发生下列 4 种事件中的任意一种，我们用 0 至 3 之间的整数 op 描述事件类型：

0 id：表示 SkyDec 往火锅里下了一个编号为 id 的食物。
1：Yazid 在锅内搜寻熟了的且最喜欢吃的食物，并拿走一个这种食物。特别地，如果锅里没有熟了的食物，那么 Yazid 会很愤怒。
2 id：YJQQQAQ 在锅内搜寻编号为 id 的食物：
- 如果锅里不存在该种食物，则 YJQQQAQ 会很愤怒；
- 如果锅里存在熟了的该食物，则 YJQQQAQ 会取走一个并食用；
- 如果锅里只有未煮熟的该种食物，那么 YJQQQAQ 会希望知道最接近煮熟的该种食物（即锅内存在时间最长的该种食物）还需要多少时间被煮熟。
3 l r：馋涎欲滴的 SkyDec 想知道，锅里编号在 [l,r] 之间的且熟了的食物总共有多少个。

解题思路

本题的关键在于如何高效地维护锅内食物的状态，以及快速地处理各种事件。我们可以使用优先队列或平衡树来存储锅内食物的信息。

数据结构选择: 使用优先队列，以食物煮熟的时间作为优先级，优先级越高的表示越先熟。同时，对于每种食物，使用一个 multiset 记录该种食物在锅内的数量和煮熟时间。
事件处理:
- op=0：将食物加入优先队列，并在对应食物的 multiset 中添加其煮熟时间。
- op=1：从优先队列中取出优先级最高（即最先熟）的食物，检查其编号是否是最小的，如果是则取走该食物并输出其编号，否则输出 'Yazid is angry.'。
- op=2：检查对应食物的 multiset，如果存在已熟的食物，则取走一个并输出 'Succeeded!'。如果存在未熟的食物，则找出 multiset 中最大（煮熟时间最晚）的元素，并输出其剩余煮熟时间。如果 multiset 为空，则输出 'YJQQQAQ is angry.'。
- op=3：遍历优先队列，统计编号在 [l,r] 之间的熟食数量，并输出结果。

代码示例

#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

const int MAXN = 100005;

int s[MAXN];
multiset<int> food[MAXN];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // 优先队列，第一个元素表示食物的煮熟时间，第二个元素表示食物的编号

int main() {
  int T;
  cin >> T;
  while (T--) {
    int n, Q;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> s[i];
    cin >> Q;
    while (Q--) {
      int t, op, id, l, r;
      cin >> t >> op;
      if (op == 0) {
        cin >> id;
        q.push({t + s[id], id}); // 将食物加入优先队列
        food[id].insert(t + s[id]); // 将食物的煮熟时间加入对应食物的 multiset
      } else if (op == 1) {
        if (q.empty()) {
          cout << "Yazid is angry." << endl;
        } else {
          pair<int, int> top = q.top();
          if (top.second == 1) {
            q.pop();
            food[top.second].erase(food[top.second].find(top.first));
            cout << top.second << endl;
          } else {
            cout << "Yazid is angry." << endl;
          }
        }
      } else if (op == 2) {
        cin >> id;
        if (food[id].empty()) {
          cout << "YJQQQAQ is angry." << endl;
        } else if (*food[id].rbegin() <= t) {
          cout << "Succeeded!" << endl;
          food[id].erase(food[id].find(*food[id].rbegin()));
        } else {
          cout << *food[id].rbegin() - t << endl;
        }
      } else {
        cin >> l >> r;
        int cnt = 0;
        while (!q.empty() && q.top().first <= t) {
          pair<int, int> top = q.top();
          q.pop();
          if (top.second >= l && top.second <= r) cnt++;
          food[top.second].erase(food[top.second].find(top.first));
        }
        cout << cnt << endl;
      }
    }
    // 清空优先队列和 multiset
    while (!q.empty()) q.pop();
    for (int i = 1; i <= n; i++) food[i].clear();
  }
  return 0;
}

优化

可以使用 map 代替 multiset，以获得更快的查找速度，但需要额外维护每个食物在 map 中的出现次数。
对于 op=3 操作，可以采用二分查找优化，以避免每次都需要遍历整个优先队列。

总结

本题是一道模拟和数据结构的综合题，需要根据题意选择合适的数据结构来维护食物的状态，并进行相应的事件处理。通过合理的数据结构和算法优化，可以有效地提高程序的效率。