每日一题之宝石组合

问题描述

在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了 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 个宝石的 “闪亮度”。

输出格式

输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。

最直接的做法就是暴力，不过只能骗骗分。

#include <iostream> #include <vector> #include <algorithm> // for max function #include <climits> // for INT_MIN using namespace std; // 计算GCD long long gcd(long long a, long long b) { if (b == 0) return a; return gcd(b, a % b); } // 计算LCM long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; // 先除后乘，避免溢出 } // 计算三个数的LCM long long lcm_three(long long a, long long b, long long c) { return lcm(lcm(a, b), c); } signed main() { long long n; cin >> n; vector<long long> a(n); for (long long i = 0; i < n; i++) { cin >> a[i]; } sort(a.begin(),a.end()); long long max_value = INT_MIN; // 初始化为极小值 long long result_a = 0, result_b = 0, result_c = 0; // 遍历所有三元组 for (long long i = 0; i < n; i++) { for (long long j = i + 1; j < n; j++) { for (long long k = j + 1; k < n; k++) { // 计算三个数的LCM long long lcm1 = lcm_three(a[i], a[j], a[k]); long long lcm2=a[i]*a[j]*a[k]; long long lcm3=lcm(a[i],a[j])*lcm(a[j],a[k])*lcm(a[i],a[k]); long long current_lcm=lcm1*lcm2/lcm3; // 更新最大值 if (current_lcm > max_value) { max_value = current_lcm; result_a = a[i]; result_b = a[j]; result_c = a[k]; } } } } // 输出结果 cout << result_a << " " << result_b << " " << result_c << endl; return 0; } 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和最大公约数相关，那么我们就去找可能的最大公约数，从最大开始找（贪心的思路），直到找到满足的三元组

#include<stdio.h> const int h=1e5; int main(){ int n; scanf("%d",&n); int mp[h+1]={0};//初始化宝石闪亮度统计表 for(int i=0;i<n;i++){ int t; scanf("%d",&t); mp[t]++;//统计亮度为t的宝石数量 } //这里我们另辟蹊径，直接枚举精美程度 for(int i=h;i>=1;i--){//枚举精美程度i int ans=0,now=0;//ans表示寻找到了几个宝石，now表示现在数组有几个宝石 int num[3];//初始化枚举到的宝石 for(int j=i;j<=h;j+=i){//对于每个精美度i，我们都需要寻找闪亮度为i，2i，3i...的宝石并统计数量 ans+=mp[j];//把寻找到的宝石数量统计起来 for(int k=0;k<mp[j]&&now<3;k++){//把统计到的宝石放到数组 num[now]=j; now++; } if(ans>=3){//如果找到了三个以上的宝石，说明存在三个宝石使其精美度为i for(int k=0;k<3;k++){ printf("%d ",num[k]); }//输出找到的三个宝石 printf("\n"); return 0; } } } }