T541155 组建队伍

关于ai辅助创作

文章的解释由ai创建

代码由本人书写，ai起辅助解释作用

代码详解与思路总结

题目回顾

题目要求：

从 $N$ 名学生中选出三位，满足以下条件：

学生的索引满足 $i < j < k$ 。
学生的能力值严格递增，即 $a_i < a_j < a_k$ 。
需要最大化三个学生能力值的乘积 $a_i \times a_j \times a_k$ 。

如果不存在满足条件的组合，输出 -1。

解题思路

1. 使用双集合维护候选值

为了高效地找到满足条件的三元组，我们使用两个有序的集合：

左集合（lset）：存储当前元素左侧所有的能力值。
右集合（rset）：存储当前元素右侧所有的能力值。

2. 遍历中间元素

从第二个元素开始，遍历到倒数第二个元素，将其作为中间的学生 $a_j$ 。对每个中间元素，执行以下步骤：

更新集合：
- 将当前元素从 rset 中移除，因为当前位置已固定为中间元素。
寻找候选的 $a_i$ 和 $a_k$ ：
- 在 lset 中寻找小于 $a_j$ 的最大值 $a_i$ 。
- 在 rset 中寻找大于 $a_j$ 的最大值 $a_k$ 。
计算并更新乘积：
- 使用找到的 $a_i$ 和 $a_k$ ，计算乘积 $a_i \times a_j \times a_k$ ，并更新最大乘积 ans。
考虑多种组合：
- 通过不同的策略组合 $a_i$ 和 $a_k$ ，确保最大化乘积，包括处理负数的情况。
将当前元素加入左集合：
- 以便在下一次迭代中作为左侧的候选元素。

3. 数据结构选取

选择 std::multiset 作为左集合和右集合的数据结构，因为它是有序的，支持高效的元素插入、删除和查找操作，时间复杂度为 $O(\log N)$ 。

4. 时间复杂度分析

初始化集合的操作耗时 $O(N \log N)$ 。
遍历过程中，每次迭代进行有限次 $O(\log N)$ 的操作，共 $O(N \log N)$ 。
总时间复杂度为 $O(N \log N)$ ，适用于题目中 $N \leq 10^5$ 的范围。

代码注释

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <set>
#include <stdexcept>

using ll = int64_t;
using std::cin, std::cout;

// 定义数组最大长度，稍微超过题目给出的最大值以防越界
const ll maxn = 1e5 + 5;

// 全局变量
ll t, n, a[maxn], ans;
ll inf = (1ll << (sizeof(inf) * 8 - 4)); // inf初始化为一个非常大的数（2^60）

int main(){
    // 加快输入输出速度，取消了C和C++程序的cin和scanf之间的同步
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> t; // 读取测试数据组数
    while(t--){
        ans = -inf; // 初始化答案为负无穷大，方便后续取最大值
        cin >> n; // 读取学生人数
        std::multiset<ll> lset, rset; // 定义两个多重集合，分别表示左侧和右侧的数据
        for(ll i = 1; i <= n; i++){
            cin >> a[i]; // 读取每个学生的能力值
            rset.emplace(a[i]); // 将所有能力值先加入右集合 rset
        }

        // 将第一个元素从右集合移到左集合
        rset.erase(rset.find(a[1]));
        lset.emplace(a[1]);

        // 从第二个元素开始遍历到倒数第二个元素
        for(ll i = 2; i < n; i++){
            rset.erase(rset.find(a[i])); // 当前元素从右集合移除，因为当前位置已经固定为中间的学生

            // 定义一个 Lambda 函数，用于检查并更新答案
            const auto check_ans = [&](const ll &a_val, const ll &b_val, const ll &c_val) -> void {
                if(a_val < b_val && b_val < c_val){ // 如果满足严格递增的条件
                    ans = std::max(ans, a_val * b_val * c_val); // 更新最大乘积
                }
            };

            {
                // 在左集合中寻找小于 a[i] 的最大值
                auto lit = lset.lower_bound(a[i]);
                if(lit == lset.end()) --lit; // 如果没找到，调整迭代器到最后一个元素
                while(*lit >= a[i] && lit != lset.begin()){
                    --lit; // 向前移动，直到找到小于 a[i] 的元素
                }
                if(*lit < a[i]){ // 确保找到的元素确实小于 a[i]
                    check_ans(*lit, a[i], *rset.rbegin()); // 检查并更新答案
                }
            }

            {
                // 在右集合中寻找大于等于 a[i] 的最小值
                if(auto it = rset.lower_bound(a[i]); it != rset.end()){
                    check_ans(*lset.begin(), a[i], *it); // 检查并更新答案
                }
            }

            // 检查左集合最小值，当前值，右集合最大值的组合
            check_ans(*lset.begin(), a[i], *rset.rbegin());

            lset.emplace(a[i]); // 将当前元素加入左集合
        }

        // 输出答案，如果 ans 没有更新过，输出 -1
        cout << (ans == -inf ? -1 : ans) << '\n';
    }
}

`check_ans` 函数详解

函数定义

const auto check_ans = [&](const ll &a_val, const ll &b_val, const ll &c_val) -> void {
    if(a_val < b_val && b_val < c_val){ // 如果满足严格递增的条件
        ans = std::max(ans, a_val * b_val * c_val); // 更新最大乘积
    }
};

功能与作用

check_ans 是一个 Lambda 表达式，用于验证并更新当前找到的三元组 (a_i, a_j, a_k) 是否满足题目要求，并在满足条件时更新全局最大乘积 ans。

具体功能：

条件检查：
- 严格递增：确认 a_val < b_val < c_val，确保三元组满足题目中的严格递增条件。
乘积计算与更新：
- 计算三者的乘积 a_val * b_val * c_val。
- 使用 std::max 比较并更新 ans，存储当前的最大乘积。

使用场景

在代码中，check_ans 被多次调用，尝试不同的三元组组合，以确保找到所有可能满足条件的组合，尤其是考虑到正负数的影响。

调用位置：

左集合中小于 a[i] 的最大值与右集合中的最大值组合：
```
check_ans(*lit, a[i], *rset.rbegin());
```
- 目的：尝试通过左集合中最大的可能小于 a[i] 的值和右集合中的最大值，构成可能的最大乘积。
左集合中的最小值与右集合中大于等于 a[i] 的最小值组合：
```
check_ans(*lset.begin(), a[i], *it);
```
- 目的：尝试通过左集合中的最小值和右集合中第一个大于等于 a[i] 的值，构成可能的最大乘积。
左集合中的最小值与右集合中的最大值组合：
```
check_ans(*lset.begin(), a[i], *rset.rbegin());
```
- 目的：尝试通过左集合中的最小值和右集合中的最大值，构成可能的最大乘积，以覆盖更多可能性。

处理正负数的依据与策略

在处理包含正数和负数的数组时，负数的存在会影响乘积的结果。具体影响如下：

正数与正数的乘积：
- 结果为正数，乘积越大越好。
负数与负数的乘积：
- 结果为正数，两个大的负数（绝对值大）相乘，可以获得较大的正数。
负数与正数的乘积：
- 结果为负数，通常不利于获得最大正数乘积。

因此，在选择三元组时，需要灵活考虑负数的组合可能性，以确保不遗漏可能得到较大乘积的组合。

具体策略：

两个负数与一个正数：
- 如果左集合中的两个负数绝对值较大，而右集合中的正数较大，这种组合可能会产生较大的正数乘积。
所有正数：
- 直接选择最大的三个正数，可能会产生最大的乘积。
避免三个负数：
- 三个负数的乘积为负数，通常不是最大正数乘积。

在代码中的体现：

多个组合尝试：
- 通过多次调用 check_ans，尝试不同的组合（包括负数与正数混合的情况），确保覆盖所有可能的三元组组合。
严格递增条件下的乘积计算：
- 任何组合都必须满足 a_i < a_j < a_k，无论这些数是正数还是负数。

示例分析

示例1：

输入：

6
-5 -4 -3 -2 -1 1

能力值数组：[-5, -4, -3, -2, -1, 1]
可能的组合：
1. (-5, -4, 1)，乘积为 20，满足条件。
2. (-3, -2, -1)，乘积为 -6，不为正数。
结果：最大乘积为 20。

示例2：

输入：

6
-5 -4 -3 1 2 3

能力值数组：[-5, -4, -3, 1, 2, 3]
可能的组合：
1. (-5, -4, 3)，乘积为 60，满足条件。
2. (1, 2, 3)，乘积为 6，满足条件但较小。
结果：最大乘积为 60。

代码如何确保正确处理

严格递增条件的统一检查：
- 无论是正数还是负数，check_ans 始终检查 a_val < b_val < c_val，确保组合的合法性。
多次组合尝试覆盖所有可能：
- 通过尝试不同的组合方式，包括左集合的最小值、最大值以及右集合的最小值、最大值，确保涵盖了包含负数和正数的所有有效组合。
利用 std::max 的特性：
- 无需提前区分正负数，直接通过 std::max 来维护全局最大的乘积，无论结果是正数还是负数。
初始化 ans 为负无穷大：
- 这样即使所有可能的乘积都是负数，最终结果也能正确反映最大值（可能为负数），若没有满足条件的组合，则输出 -1。

总结

通过使用有序的 multiset 来动态维护左右两侧的候选值，并通过多次尝试不同的三元组组合，算法能够高效地找到满足条件且乘积最大的三元组。check_ans 函数在这个过程中起到了关键作用，确保每一个候选三元组都被正确验证并且可能的最大乘积被更新。同时，通过考虑负数的特点，算法能够覆盖所有可能导致乘积最大化的情况，保证了算法的全面性和鲁棒性。

这种方法不仅满足了题目的时间复杂度要求（ $O(N \log N)$ ），还通过结构化和系统化的思路，确保了在各种输入情况下的正确性和效率。