逐日一题之宝石组合

问题描述

在一个秘密的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目标是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特别能力，可以发出不同强度的闪光。小蓝共找到了 NN 枚宝石，第 ii 枚宝石的 “闪亮度” 属性值为 HiHi​，小蓝将会从这 NN 枚宝石中选出三枚进行组合，组合之后的精美程度 SS 可以用以下公式来权衡：
S=HaHbHc⋅LCM⁡(Ha,Hb,Hc)LCM⁡(Ha,Hb)⋅LCM⁡(Ha,Hc)⋅LCM⁡(Hb,Hc)S=Ha​Hb​Hc​⋅LCM(Ha​,Hb​)⋅LCM(Ha​,Hc​)⋅LCM(Hb​,Hc​)LCM(Ha​,Hb​,Hc​)​
其中 LCMLCM 表示的是最小公倍数函数。
小蓝想要使得三枚宝石组合后的精美程度 SS 尽可能的高，请你帮他找出精美程度最高的方案。假如存在多个方案 SS 值类似，优先选择按照 HH 值升序分列后字典序最小的方案。
输入格式

第一行包含一个整数 NN 表示宝石个数。
第二行包含 NN 个整数表示 NN 个宝石的 “闪亮度”。
输特别式

输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。
最直接的做法就是暴力，不外只能骗骗分。

1. #include <iostream>
2. #include <vector>
3. #include <algorithm> // for max function
4. #include <climits>   // for INT_MIN
5. using namespace std;
7. // 计算GCD
8. long long gcd(long long a, long long b) {
9.     if (b == 0) return a;
10.     return gcd(b, a % b);
11. }
13. // 计算LCM
14. long long lcm(long long a, long long b) {
15.     return (a / gcd(a, b)) * b; // 先除后乘，避免溢出
16. }
18. // 计算三个数的LCM
19. long long lcm_three(long long a, long long b, long long c) {
20.     return lcm(lcm(a, b), c);
21. }
23. signed main() {
24.     long long n;
25.     cin >> n;
26.     vector<long long> a(n);
27.     for (long long i = 0; i < n; i++) {
28.         cin >> a[i];
29.     }
30.     sort(a.begin(),a.end());
31.     long long max_value = INT_MIN; // 初始化为极小值
32.     long long result_a = 0, result_b = 0, result_c = 0;
34.     // 遍历所有三元组
35.     for (long long i = 0; i < n; i++) {
36.         for (long long j = i + 1; j < n; j++) {
37.             for (long long k = j + 1; k < n; k++) {
38.                 // 计算三个数的LCM
39.                 long long lcm1 = lcm_three(a[i], a[j], a[k]);
40.                 long long lcm2=a[i]*a[j]*a[k];
41.                 long long lcm3=lcm(a[i],a[j])*lcm(a[j],a[k])*lcm(a[i],a[k]);
42.                 long long current_lcm=lcm1*lcm2/lcm3;
43.                 // 更新最大值
44.                 if (current_lcm > max_value) {
45.                     max_value = current_lcm;
46.                     result_a = a[i];
47.                     result_b = a[j];
48.                     result_c = a[k];
49.                 }
50.             }
51.         }
52.     }
54.     // 输出结果
55.     cout << result_a << " " << result_b << " " << result_c << endl;
56.     return 0;
57. }

复制代码

1. 公式分析

公式为：
S=HaHbHc⋅LCM(Ha,Hb,Hc)LCM(Ha,Hb)⋅LCM(Ha,Hc)⋅LCM(Hb,Hc)
最小公倍数与最大公约数（GCD）的关系：
LCM(a,b)=a⋅b/GCD(a,b)


步调 1：将 LCM 转换为 GCD

根据 LCM 和 GCD 的关系：
LCM(Ha,Hb)=Ha⋅HbGCD(Ha,Hb)
LCM(Ha,Hc)=Ha⋅HcGCD(Ha,Hc)
LCM(Hb​,Hc​)=GCD(Hb​,Hc​)Hb​⋅Hc
​​LCM(Ha,Hb,Hc)=Ha⋅Hb⋅HcGCD(Ha,Hb,Hc)
步调 2：代入公式

将上述表达式代入原公式：
S=HaHbHc⋅Ha⋅Hb⋅HcGCD(Ha,Hb,Hc)(Ha⋅HbGCD(Ha,Hb))⋅(Ha⋅HcGCD(Ha,Hc))⋅(Hb⋅HcGCD(Hb,Hc))
步调 3：简化公式

将分母和分子展开：
S=HaHbHc⋅HaHbHcGCD(Ha,Hb,Hc)HaHbHaHcHbHcGCD(Ha,Hb)⋅GCD(Ha,Hc)⋅GCD(Hb,Hc)
进一步简化：
S=HaHbHc⋅GCD(Ha,Hb)⋅GCD(Ha,Hc)⋅GCD(Hb,Hc)GCD(Ha,Hb,Hc)⋅HaHbHc
步调 4：终极简化

分子和分母中的 HaHbHcHa​Hb​Hc​ 可以约去：
S=GCD(Ha,Hb)⋅GCD(Ha,Hc)⋅GCD(Hb,Hc)GCD(Ha,Hb,Hc)

---

4. 公式的数学意义

终极推导出的公式为：
S=GCD(Ha,Hb)⋅GCD(Ha,Hc)⋅GCD(Hb,Hc)/GCD(Ha,Hb,Hc)
其实最后S就是一个和GCD(Ha,Hb,Hc)正相关的函数
既然S和最大公约数相关，那么我们就去找可能的最大公约数，从最大开始找（贪婪的思路），直到找到满足的三元组

1. #include<stdio.h>
2. const int h=1e5;
3. int main(){
4.     int n;
5.     scanf("%d",&n);
6.     int mp[h+1]={0};//初始化宝石闪亮度统计表
7.     for(int i=0;i<n;i++){
8.         int t;
9.         scanf("%d",&t);
10.         mp[t]++;//统计亮度为t的宝石数量
11.     }
12.     //这里我们另辟蹊径，直接枚举精美程度
13.     for(int i=h;i>=1;i--){//枚举精美程度i
14.         int ans=0,now=0;//ans表示寻找到了几个宝石，now表示现在数组有几个宝石
15.         int num[3];//初始化枚举到的宝石
16.         for(int j=i;j<=h;j+=i){//对于每个精美度i，我们都需要寻找闪亮度为i，2i，3i...的宝石并统计数量
17.             ans+=mp[j];//把寻找到的宝石数量统计起来
18.             for(int k=0;k<mp[j]&&now<3;k++){//把统计到的宝石放到数组
19.                 num[now]=j;
20.                 now++;
21.             }
22.             if(ans>=3){//如果找到了三个以上的宝石，说明存在三个宝石使其精美度为i
23.                 for(int k=0;k<3;k++){
24.                     printf("%d ",num[k]);
25.                 }//输出找到的三个宝石
26.                 printf("\n");
27.                 return 0;
28.             }
29.         }
30.     }
31. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。