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

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

阅读量：137 次

发布时间：2019-02-27

本文共 1206 字，大约阅读时间需要 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;