温州做网站的企业,当涂住房和城乡建设网站,wordpress如何一栏显示,深圳模具设计公司题目内容 原题链接 给定一个长度为 n n n 的数组#xff0c;选择三个下标不同元素 x , y , z x,y,z x,y,z#xff0c;问 x y z x y z \frac{xyz}{xyz} xyzxyz 的最大值和最小值是多少。
数据范围 1 ≤ n ≤ 2 ⋅ 1 0 5 1\leq n\leq 2\cdot 10^5 1≤n≤2⋅105 − 1 0 …题目内容 原题链接 给定一个长度为 n n n 的数组选择三个下标不同元素 x , y , z x,y,z x,y,z问 x y z x y z \frac{xyz}{xyz} xyzxyz 的最大值和最小值是多少。
数据范围 1 ≤ n ≤ 2 ⋅ 1 0 5 1\leq n\leq 2\cdot 10^5 1≤n≤2⋅105 − 1 0 6 ≤ x i ≤ 1 0 6 , x i ≠ 0 -10^6\leq x_i\leq 10^6,x_i\neq 0 −106≤xi≤106,xi0
题解
考虑以一个元素为自变量。 x y z x y z x y x y ⋅ 1 z 1 x y \frac{xyz}{xyz}\frac{xy}{xy}\cdot \frac{1}{z}\frac{1}{xy} xyzxyzxyxy⋅z1xy1
这里当 x x x 和 y y y 确定时极值由 z z z 确定。
显然当 z z z 取极值时该式子取到极值。
对于 x x x 和 y y y 作为自变量时也是一样的。
所以考虑取到所有的极值可以知道的是两个负数的乘积为正数所以我们需要考虑到绝对值最小和最大的数对于正数和负数来说都是最小和最大的三个数。这样至多 12 12 12 个数三重循环考虑极值即可。
时间复杂度 O ( 1 2 3 ) O(12^3) O(123)
代码
/*枚举 i 作为三个数的最中间的则在前缀和后缀中各找一个数即可
*/#include bits/stdc.h
using namespace std;const int MOD 1e9 7;int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin n;vectorint 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());vectorint 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;
}
