『JROI-1』 蒟蒻火锅的盛宴 - 算法题解

『JROI-1』 蒟蒻火锅的盛宴/n/n传说专门服务神仙们的蒟蒻火锅店前面有一首诗：/n/n灶前无用煮青山，不识神炉自往还。/n/n玉碗琼浆谁乞赐，瑶琴银箭可容攀。/n/n风生夜气通云汉，雨歇秋光上碧湾。/n/n却笑老奴真倦眼，此心空处一团闲。/n/n----/n/nQiuly 是洛谷著名餐厅“蒟蒻火锅店”的主厨，当中的伙计很多，比如呆呆的 Aw 顿顿，机智的 Cocoly1990 还有珂爱的 45dino。Qiuly 喜欢让顿顿为他准备丰富多样的食材，制作火锅的必需品包括但不限于七星章鱼和芥末鱼子酱，当然，还有各种各样珍稀而奇怪的食材：/n/n- 蒟蒻果冻制成的蒟蒻团子。/n- 糯米（雾）制成的糯米青团。/n- Aw 顿顿制成的菜鸡糕。/n- Bamboo（45dino）。/n/n这些食材难以收集，但是神仙 Qiuly 还是全部弄到手了。接下来她要让顿顿'分类这些食材'。但是顿顿是菜鸡，根本不会分类，他崩溃了。于是他请你，IOI 的 AKer，帮助他分类这些食材，因为这个问题事关 Qiuly 的成绩（IOI 第一名还是第二名），所以你必须尽快。/n/n每一个食材都有各种各样的奇怪特性，根据这些特性，Aw 顿顿咨询了全世界的专家们，评价出了'一个食材的美味程度'，根据这个程度可以'有效的分类食材'。如果你不能'在 400 毫秒内'给出答案，你就会成为一个食材，光荣的沉没在 Qiuly 精心调制的汤底中。/n/n## 题目描述/n/n有 n 个互不相同的整数，现有 m 个整数属于集合 G 中。/n/nAw顿顿规定这个集合有如下规定：/n/n- 若 x∈G，则 x+a∈G。/n- 若 x+a 不在 n 个整数中就不做处理。/n- 若对于一个集合 G 不存在需要加入的元素，那么它是完善的。/n/n若集合是完善的，输出 Great Set!，反之输出至少还要按规定加入几个食材才能完善该级别。/n/n## 输入格式/n/n第一行是一个整数 n，表示一共有 n 个整数。/n/n接下来一行存在 n 个用空格隔开的整数 A_i，'互不相同'。/n/n下一行一个正整数 m，表示集合 G 当中有 m 个整数，均属于 n 个整数当中。/n/n接下来一行是 m 个用空格隔开的整数。/n/n最后是一个正整数 a。/n/n## 输出格式/n/n如果这个集合已经完善，输出 Great Set!。/n/n反之输出需要完善该集合所需的整数数量。/n/n## 样例 #1/n/n### 样例输入 #1/n/n/n5/n1 2 3 4 5/n3/n1 3 5/n2/n/n/n### 样例输出 #1/n/n/nGreat Set!/n/n/n## 样例 #2/n/n### 样例输入 #2/n/n/n15/n13 2 10 3 1 12 8 4 5 7 9 6 15 14 11 /n7/n13 2 1 12 8 3 10 /n2/n/n/n### 样例输出 #2/n/n/n8/n/n/n## 样例 #3/n/n### 样例输入 #3/n/n/n50/n13 2 10 50 1 28 37 32 30 46 19 47 33 41 24 34 27 42 49 18 9 48 23 35 31 8 7 12 6 5 3 22 43 36 11 40 26 4 44 17 39 38 15 14 25 16 29 20 21 45 /n10/n50 46 30 32 10 2 28 37 1 13 /n3/n/n/n### 样例输出 #3/n/n/n31/n/n/n## 提示/n/n### 【样例解释】/n/n#### 样例 1 解释/n/n这个集合包含 1,3,5，其中 1+2=3，3+2=5，5+2=7 不存在，所以这个集合是完善的。/n/n#### 样例 2 解释/n/n剩下的所有整数都属于这个集合。/n/n### 【数据范围】/n/n- 1≤m<n≤6×10⁴。/n- 1≤A_i≤n。/n- 0≤a≤10⁴。/n/n### 【捆绑测试情况】/n/n|测试点编号|时间限制|分数分配|$n,m/le$| /n|:--------:|:------:|:------:|:------:| /n|$/rm Subtask 1$|$/rm 400ms$|$/rm 10pts$|$10^3$| /n|$/rm Subtask 2$|$/rm 400ms$|$/rm 15pts$|$10^4$| /n|$/rm Subtask 3$|$/rm 400ms$|$/rm 35pts$|$3/times 10^4$| /n|$/rm Subtask 4$|$/rm 400ms$|$/rm 40pts$|$6/times 10^4$| /n/n$/rm P.S.$ 这题的时限已经开到 $/rm std$ 的 15 倍，附件内有部分测试点。/n/n## 题解/n/ncpp/n#include <iostream>/n#include <vector>/n#include <unordered_set>/nusing namespace std;/n/nint main() {/n int n;/n cin >> n;/n vector<int> nums(n);/n unordered_set<int> numSet;/n for (int i = 0; i < n; i++) {/n cin >> nums[i];/n numSet.insert(nums[i]);/n }/n int m;/n cin >> m;/n vector<int> g(m);/n for (int i = 0; i < m; i++) {/n cin >> g[i];/n }/n int a;/n cin >> a;/n int count = 0;/n for (int i = 0; i < m; i++) {/n for (int j = i + 1; j < m; j++) {/n int diff = g[j] - g[i];/n int num = g[j] + diff;/n while (numSet.count(num)) {/n num += diff;/n }/n if (num <= a) {/n count++;/n }/n }/n }/n if (count == 0) {/n cout << 'Great Set!' << endl;/n } else {/n cout << count << endl;/n }/n return 0;/n}/n/n/n## 代码解释/n/n- 使用 unordered_set 来存储所有存在的整数，便于快速判断是否存在。/n- 循环遍历集合 G 中的每一个元素，并与其他元素计算差值，并根据差值找到下一个可能需要加入的元素。/n- 使用 while 循环，直到找到不在集合中的元素或者超过 a 的值。/n- 如果找到满足条件的元素，则计数器 count 加一。/n- 最后根据计数器是否为 0 来输出结果。/n/n## 优化建议/n/n- 可以考虑使用哈希表来存储集合 G 中的元素，以提高查找效率。/n- 可以使用更快的排序算法，例如快速排序或归并排序，来提高排序效率。/n/n## 总结/n/n本题是一道典型的集合完善性问题，可以使用循环和判断来实现。需要注意优化代码效率，以便在时间限制内完成任务。/n/n希望本题解对您有所帮助，如果您有任何问题，欢迎随时提问。/n