题目描述

难度分:$1446$

输入$n$（$3 \leq n \leq 2 \times 10^5$）和长为$n$的数组$a$（$-10^6 \leq a[i] \leq 10^6$且$a[i] \neq 0$）。

从$a$中选$3$个数$x$，$y$，$z$。

输出$\frac{x+y+z}{xyz}$的最小值和最大值。

和答案的绝对/相对误差需要在$10^{-12}$内。

输入样例$1$

4
-2 -4 4 5

输出样例$1$

-0.175000000000000
-0.025000000000000

输入样例$2$

4
1 1 1 1

输出样例$2$

3.000000000000000
3.000000000000000

输入样例$3$

5
1 2 3 4 5

输出样例$3$

0.200000000000000
1.000000000000000

算法

有技巧的枚举

类似的题目做多了会有种数学直觉：目标函数的最值一定是在最大的$3$个正数、最小的$3$个正数、最大的$3$个负数、最小的$3$个负数中选。

可以先把数组中的正数和负数划分到$pos$和$neg$两个数组中，为了方便获取到元素在原数组中的索引，$pos$和$neg$都采用二元组的形式存储。然后按照值的大小将$pos$和$neg$数组排序，将正数、负数对应的$top3$最值索引保存到一个$cands$数组中。由于在原数组中，正数或负数的数量不超过$5$的情况下，最大值$top3$和最小值$top3$会发生重叠，所以还要把$cands$中的索引进行去重。

有了$cands$数组，就可以在其中枚举选择$3$个元素的情况了，由于$cands$数组最大也就$12$（$top3$的正数最值不重叠，$top3$的负数最值也不重叠），因此三重循环的常数操作也才$1000$这个量级，是可以做的。

复杂度分析

时间复杂度

将数组分成正数$pos$和负数$neg$两个二元组数组并排序，时间复杂度为$O(nlog_2n)$，选出元素值$top3$大的正数索引、负数索引以及元素值$top3$小的正数索引、负数索引。由于这样的索引最多只有$12$个，因此将它们排序、去重、合并可以看成是一个比较大的常数操作。接下来三重循环枚举候选索引列表$cands$，这个列表的长度最大为$12$，三重循环就是$10^3$量级，对于$n$而言，小了$100$倍，时间复杂度的瓶颈仍然在之前的排序。因此，算法整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间的瓶颈主要在于$pos$和$neg$两个二元组数组，都是$O(n)$级别的。因此，算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;

const int N = 200010;
LL a[N];
int n;

int main() {
    scanf("%d", &n);
    vector<pair<int, int>> pos, neg;
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        if(a[i] > 0) {
            pos.push_back({a[i], i});
        }else {
            neg.push_back({a[i], i});
        }
    }
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());
    int cnt1 = pos.size(), cnt2 = neg.size();
    vector<int> prepos, sufpos, preneg, sufneg;
    for(int i = 0; i < 3; i++) {
        if(i < cnt1) {
            prepos.push_back(pos[i].second);
            sufpos.push_back(pos[cnt1 - 1 - i].second);
        }
        if(i < cnt2) {
            preneg.push_back(neg[i].second);
            sufneg.push_back(neg[cnt2 - 1 - i].second);
        }
    }
    // 将候选正数索引列表和负数索引列表合并、去重
    vector<int> posx, negx;
    for(int x: prepos) posx.push_back(x);
    for(int x: sufpos) posx.push_back(x);
    for(int x: preneg) negx.push_back(x);
    for(int x: sufneg) negx.push_back(x);
    sort(posx.begin(), posx.end());
    posx.erase(unique(posx.begin(), posx.end()), posx.end());
    sort(negx.begin(), negx.end());
    negx.erase(unique(negx.begin(), negx.end()), negx.end());
    // 合并正数和负数的候选索引列表
    vector<int> cands;
    for(int x: posx) cands.push_back(x);
    for(int x: negx) cands.push_back(x);
    int len = cands.size();
    // 枚举
    double mn = 1e12, mx = -1e12;
    for(int i = 0; i < len; i++) {
        for(int j = i + 1; j < len; j++) {
            for(int k = j + 1; k < len; k++) {
                int x = cands[i], y = cands[j], z = cands[k];
                double res = 1.0*(a[x] + a[y] + a[z]) / (1.0*a[x]*a[y]*a[z]);
                mn = min(mn, res);
                mx = max(mx, res);
            }
        }
    }
    printf("%.15lf\n%.15lf\n", mn, mx);
    return 0;
}