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

这篇具有很好参考价值的文章主要介绍了【每日一题】ARC158B - Sum-Product Ratio | 数学 | 中等。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目内容

原题链接

给定一个长度为 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 1n2105
  • − 1 0 6 ≤ x i ≤ 1 0 6 , x i ≠ 0 -10^6\leq x_i\leq 10^6,x_i\neq 0 106xi106,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+yz1+xy1

这里当 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)文章来源地址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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 每日一题(相交链表 )

    欢迎大家来我们主页进行指导 LaNzikinh-CSDN博客 160. 相交链表 - 力扣(LeetCode) 给你两个单链表的头节点  headA  和  headB  ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回  null  。 图示两个链表在节点  c1  开始相交 : 题目数据  保证  整

    2024年04月11日
    浏览(33)
  • [每日一题] 01背包问题

    给定 n 种物品和一背包。物品 i 的重量是 w i w_i w i ​ ,其价值为 v i v_i v i ​ ,背包的容量为 C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 对于一种物品,要么装入背包,要么不装。 解法一:暴力递归 可能性分析: f ( i, rest ) 物品 i ,背包容量为

    2024年02月11日
    浏览(36)
  • C语言每日一题

    今天分享的是一道牛客网上面的题目,链接在下面 有序序列合并 这道题做法有很多,最简单的是合并一起,然后用排序就行了,今天将一个最高效的办法,思路是两个数组第一项进行比较,小的先输出,输出的那个数组的下标往后移动,然后再进行比较,如果是另一个数组

    2024年02月12日
    浏览(36)
  • leetcode每日一题44

    图论 dfs/bfs dfs代码框架 思路:本题要求找到被x围绕的陆地,所以边界的陆地O肯定不符合条件。那么我们只要从周边找到陆地O然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地O都变成A,然后再去重新遍历地图的时候,把剩下的O变成X,再把所有的A变成O。 确认递归函数,参数

    2024年01月19日
    浏览(43)
  • 每日一题,杨辉三角

    给定一个非负整数 numRows,生成「杨辉三角」的前 numRows 行。 示例 1: 示例 2:

    2024年02月04日
    浏览(36)
  • 【每日一题】57. 插入区间

    给你一个 无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 示例 2: 示例 3: 示例 4: 示例 5: 提示: 0 = intervals.length = 104 intervals[i].length == 2 0 = interval

    2024年02月10日
    浏览(42)
  • 每日一题 — 二分查找

    704. 二分查找 - 力扣(LeetCode)   朴素二分查找模板:  代码:

    2024年04月23日
    浏览(31)
  • C语言——每日一题

    倒置字符串 要将每一个单词逆序输出,首先可以将整个字符串内容都逆序输出,然后再将字符串中的每一个单词再进行逆序。 例如:逆序 i like beijing. 先逆序成: .gnijieb ekil i 再将每个单词逆序: beijing. like i 1.1 字符串的读取 先创建一个字符数组: char arr[101]; (因为题目中

    2024年02月07日
    浏览(36)
  • 【每日一题】56. 合并区间

    以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。 示例 1: 示例 2: 提示: 1 = intervals.length = 104 intervals[i].length == 2 0 = starti = endi = 104 首先将所

    2024年02月10日
    浏览(34)
  • 【每日一题】最大交换

    【暴力法】【贪心法】【数组】【2024-01-22】 670. 最大交换 本题的数据规模比较小,暴力法也可以通过。以下将会介绍暴力法和本题最优法。 思路 对于整数 num 的十进制数位最长只有八位,交换任意两个数位最多有 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 7+6+5+4+3+2+1=28 7 + 6 + 5 + 4 + 3 + 2 + 1 = 2

    2024年01月24日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包