2014J_2：比例简化

洛谷：P2118
OJ： P4943

代码分析

  1. 输入处理：
    • 读取支持人数 A、反对人数 B 和最大比例上限 L。
  2. 初始化变量：
    • 使用 min_diff_num = -1 记录最小差值。这里用 -1 初始化是为了方便后续比较是否有找到更小的比例差。
    • 变量 min_n 和 min_d 分别记录最终化简后的分子和分母。
  3. 枚举可能的分母 d：
    • 枚举 d 从 1 到上限 L。
    • 对于每个分母 d，计算使得 n / d >= A / B 的最小 n，公式为：cpp复制代码long long n_min = (A * d + B - 1) / B; 这个公式是为了向上取整，确保 n / d 大于等于 A / B。
  4. 寻找互质的分子 n：
    • 从 n_min 开始尝试寻找符合条件的 n，且保证 gcd(n, d) == 1。
    • 一旦找到符合条件的 n，就计算当前比例的差值：cpp复制代码long long diff_num = n * B - A * d;
    • 比较是否找到了更小的差值，如果是则更新最优的分子和分母。
  5. 优化部分：
    • 跳出循环：由于我们已经找到了最小的 n，所以可以直接跳出 n 的循环，减少不必要的计算。
    • 更简洁的初始化：使用 -1 初始化差值方便后续的条件判断，避免复杂的比较逻辑。
  6. 输出结果：
    • 最后输出最优的 n 和 d，即化简后的比例。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**************************************************************** 
 * Description: 2014普及组  比例简化
 * Author: Alex Li
 * Date: 2024-10-09 22:45:16
 * LastEditTime: 2024-10-09 22:45:29
****************************************************************/
#include <iostream>
#include <algorithm>
#define LL long long

using namespace std;

// 计算最大公约数（GCD）的函数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    freopen("ratio.in","r",stdin);
    freopen("ratio.out","w",stdout);
    // 输入支持人数 A，反对人数 B，以及比例上限 L
    LL A, B, L;
    cin >> A >> B >> L;

    // 初始化用于存储最小差值的变量
    LL min_diff_num = -1; // 用于记录最小差值的分子部分
    LL min_n = 0, min_d = 1; // 分别记录化简后的分子和分母

    // 枚举可能的分母 d，范围从 1 到 L
    for (LL d = 1; d <= L; ++d) { 
        // 计算使得 n/d >= A/B 的最小 n 值，这个写法是为了向上取整，确保 n / d 大于等于 A / B。
        LL n_min = (A * d + B - 1) / B;  
        if (n_min > L) continue; // 如果 n_min 超过上限 L，则跳过当前分母 d

        // 尝试从 n_min 开始寻找最小的 n，使得 gcd(n, d) == 1
        for (LL n = n_min; n <= L; ++n) {
            if (gcd(n, d) == 1) { // 确保 n 和 d 互质
                // 计算差值的分子部分：n * B - A * d
                LL diff_num = n * B - A * d;

                // 如果找到的差值更小，则更新最优结果
                if (min_diff_num == -1 || diff_num * min_d < min_diff_num * d) {
                    min_diff_num = diff_num; // 更新最小差值
                    min_n = n; // 更新最优分子
                    min_d = d; // 更新最优分母
                }
                break; // 因为 n_min 已是最小 n，因此可以直接跳出循环
            }
        }
    }

    // 输出化简后的比例结果
    cout << min_n << " " << min_d << endl;

    return 0;
}
Previous Topic
Back to Lesson
Next Topic