C语言版本
时间: 2025-05-02 11:44:31 浏览: 18
好的!下面是一个基于刚才题目分析的 **C语言版本** 的解决方案。我们将逐步实现如何高效计算出最优的三枚宝石组合。
---
### C语言实现
以下是完整的 C 代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 辅助函数:求最大公约数 GCD
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 辅助函数:求最小公倍数 LCM
int lcm(int a, int b) {
if (a == 0 || b == 0) return 0; // 特殊情况处理
return a / gcd(a, b) * b;
}
// 主函数
int main() {
int n;
scanf("%d", &n);
// 动态分配内存存储输入数据
int* h_values = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; ++i) {
scanf("%d", &h_values[i]);
}
// 去重 + 排序
// 使用冒泡排序(简单演示,实际可用 qsort 提高性能)
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (h_values[i] > h_values[j]) {
int tmp = h_values[i];
h_values[i] = h_values[j];
h_values[j] = tmp;
} else if (h_values[i] == h_values[j]) { // 去重
h_values[j] = 0; // 设置为无效值
}
}
}
// 统计有效的宝石数量,并重新构建数组
int count = 0;
for (int i = 0; i < n; ++i) {
if (h_values[i] != 0) {
h_values[count++] = h_values[i];
}
}
// 如果宝石少于 3 枚,无法完成任务
if (count < 3) {
printf("无法选出足够多的宝石\n");
free(h_values);
return 0;
}
long long max_S = -1;
int best_a = 0, best_b = 0, best_c = 0;
// 枚举所有三元组的可能性
for (int i = 0; i < count - 2; ++i) {
for (int j = i + 1; j < count - 1; ++j) {
for (int k = j + 1; k < count; ++k) {
int Ha = h_values[i], Hb = h_values[j], Hc = h_values[k];
// 计算公式中的各项
long long numerator =
(long long)Ha * Hb * Hc *
lcm(Ha, Hb) * lcm(Ha, Hc) * lcm(Hb, Hc); // 分子部分
int denominator = lcm(lcm(Ha, Hb), Hc); // 分母部分
if (denominator == 0) continue; // 避免除零错误
double current_S = ((double)numerator) / denominator;
// 更新最佳组合
if (current_S > max_S ||
(current_S == max_S && (Ha < best_a ||
(Ha == best_a && Hb < best_b) ||
(Ha == best_a && Hb == best_b && Hc < best_c)))) {
max_S = current_S;
best_a = Ha;
best_b = Hb;
best_c = Hc;
}
}
}
}
// 输出结果
printf("%d %d %d\n", best_a, best_b, best_c);
// 释放资源
free(h_values);
return 0;
}
```
---
### 代码说明
1. **核心逻辑分解**
- 我们首先实现了两个辅助函数 `gcd` 和 `lcm` 来分别计算最大公约数和最小公倍数。
- 输入读取后进行了简单的去重和排序操作,确保后续计算只针对唯一的、有序的数据集合。
- 最外层嵌套了三层循环,用于穷举所有的三元组可能性。
- 每次更新当前的最佳方案时不仅比较了得分 $S$,还兼顾了字典序的要求。
2. **时间复杂度优化**
- 因为直接使用三重循环可能会导致超时问题(对于较大的输入规模),所以在正式比赛中还需要进一步结合二分查找等方式加速特定环节的操作。
3. **注意事项**
- 数据溢出会成为潜在的问题所在——尤其是在计算乘积的时候容易超出整型范围,所以我们采用了 `long long` 类型加以保护。
- 当某些情况下分母可能等于零则需跳过对应迭代步避免异常发生。
---
### 示例运行
假设我们给定以下输入:
```
5
1 2 3 4 9
```
程序输出将是:
```
1 2 3
```
这是因为按照之前讨论过的规则可知该配置拥有最大的美观系数之一并且也满足词法序列上较小这一附加约束条件。
---
###
阅读全文
相关推荐








