题目内容
原题链接
给定一个长度为 n n n 的数组,选择三个下标不同元素 x , y , z x,y,z x,y,z,问 x + y + z x y z \frac{x+y+z}{xyz} xyzx+y+z 的最大值和最小值是多少。
数据范围
- 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,xi=0
题解
考虑以一个元素为自变量。
x + y + z x y z = x + y x y ⋅ 1 z + 1 x y \frac{x+y+z}{xyz}=\frac{x+y}{xy}\cdot \frac{1}{z}+\frac{1}{xy} xyzx+y+z=xyx+y⋅z1+xy1
这里当 x x x 和 y y y 确定时,极值由 z z z 确定。
显然当 z z z 取极值时,该式子取到极值。
对于 x x x 和 y y y 作为自变量时,也是一样的。
所以考虑取到所有的极值,可以知道的是,两个负数的乘积为正数,所以我们需要考虑到绝对值最小和最大的数,对于正数和负数来说都是最小和最大的三个数。这样至多 12 12 12 个数,三重循环考虑极值即可。文章来源:https://www.toymoban.com/news/detail-731878.html
时间复杂度: O ( 1 2 3 ) O(12^3) O(123)文章来源地址https://www.toymoban.com/news/detail-731878.html
代码
#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;
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;
}
到了这里,关于【每日一题】ARC158B - Sum-Product Ratio | 数学 | 中等的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!