AcWing寒假每日一题——Day31比例简化-白红宇

AcWing寒假每日一题——Day31比例简化

阅读量：137 次

发布时间：2019-02-27

本文共 1227 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要将支持人数A和反对人数B的比例A:B化简为A':B'，使得A'和B'不超过给定的上限L，并且A'和B'互质。同时，我们需要确保化简后的比例尽可能接近原比例，并且乘积A'B'尽可能接近A*B。

方法思路

问题分析：我们需要找到一个比例A':B'，使得它与原比例A:B尽可能接近，同时满足A'和B'不超过给定的上限L，并且互质。

双重循环遍历：我们遍历所有可能的A'和B'的值，范围都是从1到L。

互质检查：对于每对(A', B')，检查它们是否互质（最大公约数为1）。

比例差异计算：计算每对(A', B')的比例与原比例的差异，记录最小的差异对应的A'和B'。

优化选择：在差异相同的情况下，选择比例更大的A':B'。

解决代码

#include 
   
    
using namespace std;
int a, b, l, best_a, best_b;
double ratio = (double)a / b;
double min_diff = 1e9;
for (int i = 1; i <= l; ++i) {
    for (int j = 1; j <= l; ++j) {
        if (gcd(i, j) != 1) continue;
        double current_ratio = static_cast
    
     (i) / j;
        double diff = abs(current_ratio - ratio);
        if (diff < min_diff) {
            min_diff = diff;
            best_a = i;
            best_b = j;
        } else if (diff == min_diff) {
            if (static_cast
     
      (i) / j > ratio) {
                best_a = i;
                best_b = j;
            }
        }
    }
}
cout << best_a << " " << best_b;

代码解释

输入处理：读取输入的支持人数A、反对人数B和上限L。

比例计算：计算原比例ratio = A/B。

双重循环遍历：遍历所有可能的A'和B'，范围从1到L。

互质检查：使用gcd函数检查当前A'和B'是否互质。

比例差异计算：计算当前比例与原比例的差异，记录最小的差异对应的A'和B'。

优化选择：在差异相同的情况下，选择比例更大的A':B'。

输出结果：打印最优化的A'和B'。

这种方法确保了我们找到一个尽可能接近原比例且满足条件的化简比例。

转载地址：http://lisb.baihongyu.com/

你可能感兴趣的文章