7、最大比例

题目 最大比例

思路分析

有点像数论里那道等差的 求什么最大公约数

然后就照着这个gcd的思路随便蒙了一下

排序 相邻元素一定存在一个公比 找最大的公比 然后化简

过了一个……

#include<bits/stdc++.h>

using namespace std;

const int N=110;

int a[N];

int main() {

    int n; cin >> n;

    for(int i = 0; i < n; i++)

        cin >> a[i];

    sort(a, a + n);

    int maxq = -1, fm = 0, fz = 0;

    for(int i = 0; i + 1 < n; i++) {

        if(a[i] == 0)

            continue;

        int curq = a[i + 1] / a[i];

        if(curq > maxq) {

            maxq = curq;

            fm = i + 1;

            fz = i;

        }

    }

    int maxgcd = __gcd(a[fm], a[fz]);

    if(maxgcd == 0)

        maxgcd = 1;

    cout << a[fm] / maxgcd << "/" << a[fz] / maxgcd << endl;

    return 0;

}

我草 居然真可以这样写

不过思路应该是这样

要找到最小的公比 因为整个数列是等比的 如果公比大了 就不能让所有的数满足等比性质

所以要找到一个能让所有数都满足的公比

把判断改成乘法 避免精度丢失

没必要存储maxq 只需要一直迭代能获得最大公比的分母和分子就行了

后面就和前面一样了 去求最大公因数 做一个约分

#include<bits/stdc++.h>

using namespace std;

const int N=110;

long long a[N];

int main() {

    int n; cin >> n;

    for(int i = 0; i < n; i++)

        cin >> a[i];

    sort(a, a + n);

    long long fz = 0, fm = 1;

    for(int i = 0; i + 1 < n; i++) {

        if(fz * a[i + 1] < fm * a[i] && a[i] != a[i+1]) {

            fz = a[i];

            fm = a[i + 1];

        }

    }

    long long maxgcd = __gcd(fz, fm);

    cout << fm / maxgcd << "/" << fz / maxgcd << endl;

    return 0;

}

就……这样……过了？

就……这样……ak了？？？

emmm 这道题确实是 我自己都不知道为什么就可以这样写 真就是蒙 这就是贪心吗

经验教训呢 是 考试时有时间多的话 贪心问题有想法就想办法完善一下 因为一开始的试试看的方案很多漏洞

把这些漏洞补全 考虑周到些 说不定就ac了呢 hh

另外 前面还有一道题 凑算式 也是用到了除法 对于这种除法的判断 都不能直接去做 他会自己取整 不可靠

要把除法转变成乘法进行判断

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=110;

long long a[N];

int main() {

    int n; cin >> n;

    for(int i = 0; i < n; i++)

        cin >> a[i];

    sort(a, a + n);

    long long fz = 0, fm = 1;

    for(int i = 0; i + 1 < n; i++) {

        if(fz * a[i + 1] < fm * a[i] && a[i] != a[i+1]) {

            fz = a[i];

            fm = a[i + 1];

        }

    }

    long long maxgcd = __gcd(fz, fm);

    cout << fm / maxgcd << "/" << fz / maxgcd << endl;

    return 0;

}

同类题型

视频讲解

⬅️ 6、交换瓶子 🏠 00-刷题理模型 ➡️ 第七届 c++ B组 省赛