【每日一题】ARC158B - Sum-Product Ratio | 数学 | 中等

题目内容

原题链接

给定一个长度为 $n$ 的数组，选择三个下标不同元素 $x,y,z$，问 $\frac{x+y+z}{xyz}$ 的最大值和最小值是多少。

数据范围

• $1\le n\le 2\cdot 10^5$
• $-10^6\le x_i\le 10^6,x_i\ne 0$

题解

考虑以一个元素为自变量。

$\frac{x+y+z}{xyz}=\frac{x+y}{xy}\cdot \frac{1}{z}+\frac{1}{xy}$

这里当 $x$ 和 $y$ 确定时，极值由 $z$ 确定。

显然当 $z$ 取极值时，该式子取到极值。

对于 $x$ 和 $y$ 作为自变量时，也是一样的。

所以考虑取到所有的极值，可以知道的是，两个负数的乘积为正数，所以我们需要考虑到绝对值最小和最大的数，对于正数和负数来说都是最小和最大的三个数。这样至多 $12$ 个数，三重循环考虑极值即可。

时间复杂度：$O(12^3)$

代码

#include 
using namespace std;

const int MOD = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> pos, neg;
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        if (x > 0) pos.push_back(x);
        else neg.push_back(x);
    }

    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());

    vector<int> arr;
    int m = min(int(pos.size()), 3);
    for (int i = 0; i < m; ++i) arr.push_back(pos[i]);
    m = max(m, int(pos.size()) - 3);
    for (int i = m; i < pos.size(); ++i) arr.push_back(pos[i]);

    m = min(int(neg.size()), 3);
    for (int i = 0; i < m; ++i) arr.push_back(neg[i]);
    m = max(m, int(neg.size()) - 3);
    for (int i = m; i < neg.size(); ++i) arr.push_back(neg[i]);

    double max_ans = 1.0 * (arr[0] + arr[1] + arr[2]) / (1ll * arr[0] * arr[1] * arr[2]);
    double min_ans = max_ans;
    for (int i = 0; i < arr.size(); ++i)
        for (int j = i + 1; j < arr.size(); ++j)
            for (int k = j + 1; k < arr.size(); ++k) {
                double v = 1.0 * (arr[i] + arr[j] + arr[k]) / (1ll * arr[i] * arr[j] * arr[k]);
                max_ans = max(max_ans, v);
                min_ans = min(min_ans, v);
            }

    cout << setprecision(15) << min_ans << "\n" << max_ans << "\n";

    return 0;
}
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