Description
在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某观点表示支持的有 1498 人，反对的有 902 人，那么其比例可以简单地记为1498∶902。 因该比例的数值太大，难以一眼看出它们的关系。若把比例记为 5∶3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。 现给出支持人数 A 和反对人数 B，以及一个上限 L，请将 A 比 B 化简为 A′ 比 B′，要求在 A′和 B′ 均不大于 L，且 A′ 和 B′ 互质（两个整数的最大公约数为 1）的前提下，A′/B′≥ A/B 且 A′/B′-A/B 的值尽可能小。
Input
一行三个整数 A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。
Output
一行两个整数 A′ 和 B′，中间用一个空格隔开，表示化简后的比例。
Accepted Code
#include <bits/stdc++.h>
using namespace std;
int gcd(int x, int y) //欧几里得算法求最大公因数
{
int rem = 0;
while (y > 0)
{
rem = x % y;
x = y;
y = rem;
}
return x;
}
int main()
{
double a, b, l;
cin >> a >> b >> l;
double h = a / b;
double minm = 1000;
int ans1 = 1, ans2 = 1;
for (int a1 = 1; a1 <= l; a1++) //双循环暴力枚举获取两数的所有可能
{
for (int b1 = 1; b1 <= l; b1++)
{
if (((double)a1 / (double)b1 >= h) && (minm - h > ((double)a1 / (double)b1) - h))
{
minm = (double)a1 / (double)b1;
ans1 = a1;
ans2 = b1;
}
}
}
int y = gcd(ans1, ans2);
cout << ans1 / y << " " << ans2 / y << endl;
return 0;
}
解后反思
本题略为有趣，本蒟蒻WA了足足五次，后来一顿乱改就过了，评测姬玄学错误。
再说这一题，暴力复杂度大约是1e4，完全可以接受，那就暴力遍历枚举，记录下差值，获取最小的一组最后gcd化简即可