• 日期: 2028-05-19
  • 标签: 常规

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

题目背景

SkyDec 和 YJQQQAQ 都是 Yazid 的好朋友。他们都非常喜欢吃火锅。有一天，他们聚在一起，享受一场火锅盛宴。

题目描述

在这场火锅盛宴中，有一个麻辣浓汤锅底的火锅和 'n' 种食物，每种食物数量都是无限的。我们用 1 至 'n' 将这些食材编号。

每种食物煮熟所需要的时间不同，第 'i' 种食物煮熟需要 's_i' 单位时间。这表示如果你在第 'T' 个时刻将一个食物 'i' 下到火锅里，那么它会在第 'T+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']' 之间的且熟了的食物总共有多少个。

输入格式

从标准输入读入数据。

本题包含多组数据，输入的第一行为一个正整数 'T'，表示数据组数。接下来依次描述每组数据，对于每组数据：

第一行一个正整数 'n'，表示食物的种类数。

第二行 'n' 个用空格隔开的正整数 's_1,s_2,···, s_n'，描述每种食物煮熟需要的时间。

第三行一个正整数 'Q'，表示事件的数目。

接下来 'Q' 行，每行若干个用空格隔开的非负整数，描述一个事件。先是两个整数 't,op'，分别表示发生事件的时间以及事件的类型。

  • 如果 'op=0' 或 'op=2'，则接下来 1 个正整数 'id'，意义见题目描述；
  • 如果 'op=1'，则接下来没有其他数；
  • 如果 'op=3'，则接下来 2 个正整数 'l,r'，意义见题目描述。

数据保证 't' 按输入顺序严格递增。

输出格式

对于每个 'op≠0' 的操作，输出一行表示答案。对于不同的 'op'，需要输出的内容如下：

  • 对于 'op=1'，如果 Yazid 成功取走食物，则输出他取走食物的编号；否则输出 '‘Yazid is angry.’'（不含引号，下同）。
  • 对于 'op=2'，如果 YJQQQAQ 成功取走食物，则输出 '‘Succeeded!’'；否则，如果锅里有未煮熟的该类食物，输出最接近煮熟的该种食物还需要多少时间被煮熟；否则，输出 '‘YJQQQAQ is angry.’'。
  • 对于 'op=3'，输出锅内编号在指定范围内的熟食的数量。

样例 #1

样例输入 #1

1
2
1 100
10
1 0 2
2 0 1
3 2 1
4 2 2
5 2 1
200 0 1
201 3 1 2
202 1
203 1
204 1

样例输出 #1

Succeeded!
97
YJQQQAQ is angry.
2
1
2
Yazid is angry.

提示

对于所有数据，保证 'T≤4'，保证 'n≤100,000'，'Q≤500,000'，'1≤s_i≤10^8'，'1≤t≤10^9'，'op∈{0, 1, 2, 3}'，'1≤id≤n'，'1≤l≤r≤n'。数据保证 't' 按输入顺序严格递增。

来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/王聿中 命题/王聿中 验题/吕时清，杨景钦

Git Repo：https://git.thusaac.org/publish/CodePlus201712

感谢腾讯公司对此次比赛的支持。

内容：Test Input Reasoning:

测试最小规模的数据，'n=1'。

算法思路

  1. 数据结构选择: 由于需要高效地处理各种事件，可以使用优先队列 (priority queue) 来存储所有食物的状态，并根据煮熟时间排序。另外，可以使用一个哈希表 (hash table) 来记录每种食物在锅内的数量以及它们被煮熟的时间。

  2. 事件处理: 对于每种事件，使用对应的逻辑进行处理：

    • 下食物 ('op=0'): 将食物加入优先队列，并更新哈希表中的对应记录。
    • Yazid 取食物 ('op=1'): 从优先队列中取出最早煮熟的食物，如果该食物存在且已经煮熟，则输出该食物的编号；否则，输出 '‘Yazid is angry.’'。
    • YJQQQAQ 取食物 ('op=2'): 在哈希表中查找对应食物，如果存在且已煮熟，则输出 '‘Succeeded!’'；如果存在但未煮熟，则输出最接近煮熟的时间；否则输出 '‘YJQQQAQ is angry.’'。
    • 查询熟食数量 ('op=3'): 利用优先队列，找出所有在指定范围内的已煮熟的食物，并计算总数量。

代码实现 (C++)

#include <iostream>
#include <queue>
#include <unordered_map>
#include <algorithm>

using namespace std;

struct Food {
    int id; // 食物编号
    int time; // 煮熟时间
    bool operator<(const Food &other) const {
        return time > other.time; // 优先队列按时间排序 (最早煮熟的排在前面)
    }
};

int main() {
    int T, n, Q, t, op, id, l, r;
    cin >> T;
    while (T--) {
        cin >> n;
        vector<int> s(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> s[i];
        }
        cin >> Q;

        priority_queue<Food> pq; // 优先队列，存储食物信息
        unordered_map<int, pair<int, int>> food_info; // 哈希表，记录食物数量和煮熟时间

        while (Q--) {
            cin >> t >> op;
            if (op == 0) {
                cin >> id;
                pq.push({id, t + s[id]}); // 下食物
                if (food_info.count(id)) {
                    food_info[id].first++; // 更新食物数量
                } else {
                    food_info[id] = {1, t + s[id]}; // 新的食物
                }
            } else if (op == 1) {
                if (!pq.empty() && pq.top().time <= t) { // 判断是否有熟食
                    cout << pq.top().id << endl;
                    food_info[pq.top().id].first--;
                    pq.pop();
                    if (food_info[pq.top().id].first == 0) {
                        food_info.erase(pq.top().id);
                    }
                } else {
                    cout << '‘Yazid is angry.’' << endl;
                }
            } else if (op == 2) {
                cin >> id;
                if (food_info.count(id)) {
                    if (food_info[id].second <= t) { // 已煮熟
                        cout << '‘Succeeded!’' << endl;
                        food_info[id].first--;
                        if (food_info[id].first == 0) {
                            food_info.erase(id);
                        }
                    } else { // 未煮熟
                        cout << food_info[id].second - t << endl; // 输出剩余时间
                    }
                } else {
                    cout << '‘YJQQQAQ is angry.’' << endl;
                }
            } else { // op == 3
                cin >> l >> r;
                int count = 0;
                while (!pq.empty() && pq.top().time <= t) { // 遍历优先队列
                    if (pq.top().id >= l && pq.top().id <= r) { // 在指定范围内
                        count++; // 计数
                        food_info[pq.top().id].first--;
                        pq.pop();
                        if (food_info[pq.top().id].first == 0) {
                            food_info.erase(pq.top().id);
                        }
                    } else { // 不在指定范围内
                        pq.pop();
                    }
                }
                cout << count << endl;
            }
        }
    }
    return 0;
}

性能优化

  • 使用优先队列: 优先队列可以高效地找出最早煮熟的食物，并帮助处理 Yazid 取食物的操作。
  • 使用哈希表: 哈希表可以快速查找食物信息，并帮助处理 YJQQQAQ 取食物和查询熟食数量的操作。
  • 优化优先队列: 当食物被取走或煮熟后，可以及时从优先队列中删除，避免不必要的遍历。
  • 优化哈希表: 当食物被取走或数量变为 0 时，可以及时从哈希表中删除，避免不必要的查找。

总结

本题是一道模拟算法题，需要仔细考虑各种事件的处理方式，并使用合适的 data structures 和算法来提高效率。通过优先队列、哈希表等数据结构，可以有效地管理食物信息，并快速处理各种操作。此外，还可以通过一些优化手段，进一步提高程序的运行效率。

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

原文地址: http://www.cveoy.top/t/topic/f4C 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录