GESP2026年6月认证C++五级( 第三部分编程题（2、晚宴））精讲

第三部分 第二题——《晚宴》

第一幕：美食晚宴开始了

1、有一天，小明参加了一场五星级晚宴。

桌子上摆着很多菜。

每道菜都有一个"美味度"。

（1）例如：

3 5 7 35 105

（2）主持人宣布了一个规则：

小明只能选两道菜，而且必须是两道菜。

而且还有一个特殊要求：

这两道菜必须互质！

（3）小明的目标是：

按照规则选，让两道菜的美味度之和最大。

第二幕：什么叫互质？

1、有的学生一看到：

互质

脑子一片空白。

其实非常简单。

2、老师拿出几个数字。

第一组

3 5

最大公约数：

gcd(3,5) = 1

所以：

互质

可以一起吃。

第二组

6 9

最大公约数：

3

不是：

1

所以：

不能一起选。

第三组

8 15

最大公约数：

1

是可以的。

3、互质 ： gcd==1

以后看到：

互质

脑子立刻翻译成：

gcd(a,b)==1

这是学习数论最重要的结论之一。

第三幕：先不要写程序

1、先看样例。

3 5 7 35 105

2、我们先人工找一下。

（1）第一对：

3 5

互质。

和是：

8

（2）第二对：

3 7

互质。

和是：

10

（3）第三对：

35 7

最大公约数：

7

失败。

（4）第四对：

35 105

最大公约数：

35

失败。

（5）第五对：

5 35

最大公约数：

5

失败。

（6）继续……

最后发现：

3 35

互质。

和：

38

这是最大的。

（7）所以答案：

38

和样例一致。

第四幕：本题能用暴力枚举吗？

可以！

1、如果有5道菜。

3 5 7 35 105

2、每两道菜，都试一次。

3 5 3 7 3 35 3 105 5 7 5 35 ……

所有组合。

都检查。

3、暴力枚举的时间复杂度：

O(N^2)

本题中 2 <= n <= 1000,

完全没问题。

第五幕：使用两层循环：

1、外层循环：

第一个数

2、内层循环：

第二个数

3、代码：

for(i) for(j)

就是：

所有组合。

第六幕：如何更新答案？

1、我们先定义一个：

ans

开始：

0

2、现在：

第一组。

3 5

合法。

和：

8

3、于是：

ans = 8

4、下一组：

3 7

合法。

10

比：

8

大。

更新。

ans = 10

5、于是：

程序就是：

if(gcd(...)==1) ans=max(ans,a+b);

答案就按照我们的要求更新了。

第七幕：重点要写gcd 函数

1、因为：

互质

判断的是：

最大公约数。

2、所以要写：

gcd

函数来求最大公约数。

3、使用欧几里得算法：

int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); }

第八幕：完整代码

#include <iostream> #include <algorithm> using namespace std; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } int main() { int n; cin>>n; int a[1010]; for(int i=0;i<n;i++) cin>>a[i]; int ans=0; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(gcd(a[i],a[j])==1) { ans=max(ans,a[i]+a[j]); } } } cout<<ans<<endl; return 0; }

利用两层循环枚举所有两两组合，判断是否互质，如果互质就更新最大答案。

第九幕：程序复杂度分析

1、题目中：

n <= 1000

2、两层循环：

1000×1000 ≈100万

3、每次：

gcd

复杂度：

O(logV)

4、总复杂度：

O(n² logV)

对于本题的数据范围是完全可以通过的。

本题要掌握的知识（★★★★★）

这道题考点，首先就是要掌握gcd()函数，还要有正确的思维流程：

① 枚举所有可能方案 ↓ ② 判断是否合法 ↓ ③ 如果合法 ↓ ④ 更新最优答案

朴素算法模板

遇到类似"从很多方案中找到最优方案"的问题，可以想到下面这个模板：

ans = 初始值; for(枚举所有方案) { if(方案合法) { ans = max(ans, 当前方案); } }

这道《晚宴》就是这个基础模板的应用。