分组（version 2） - 题解

标签与难度

标签: 动态规划, 排序, 组合优化, 枚举难度: 2500

题目大意喵~

主人你好呀~！这道题是说，我们有 $n$ 个学生，每个学生有个成绩 $a_i$ 。我们要把他们分成好几组，但是有几个规矩哦：

每个小组的人数 $y$ 都必须是奇数，并且在给定的范围 $[l, r]$ 内。
一个小组的分数是这么算的：先把组成员的成绩排个序，取中位数 $x$ 。然后用这个中位数和一个给定的值 $b_y$ 做异或运算，也就是 $x \oplus b_y$ 。
一个分组方案的总分，是所有小组分数的平均值。

我们的任务，就是找到一种分组方法，让这个平均分最大化！最后输出这个最大平均分向下取整的结果。如果根本没法按要求分组，就输出 -1，喵~

解题思路分析

这道题想让我们最大化一个平均值， $\frac{\sum \text{小组分值}}{\text{小组数量}}$ 。这种形式通常有点棘手，因为分母（小组数量）不是固定的。

一个很自然的想法是，如果我们能固定小组的数量就好了！所以，我们可以尝试枚举小组的数量，设为 $s$ 吧。

当小组数量 $s$ 固定后，问题就变成了：如何将 $n$ 个学生分成 $s$ 个小组，使得所有小组的分值总和最大。因为分母 $s$ 固定了，最大化平均值就等价于最大化分子（总和），对吧？

好，现在问题变成了：从 $n$ 个学生中，选出 $s$ 组符合要求的学生，使得分值总和最大。

为了方便处理中位数，我们第一步肯定是要把所有学生的成绩 $a_i$ 从小到大排序。排序之后，如果我们选定学生 $i$ （成绩为 $a_i$ ）作为某个小组的中位数，这个小组的大小为 $y = 2k+1$ 。那么为了构成这个小组，我们还需要再选 $k$ 个成绩比 $a_i$ 小的同学，和 $k$ 个成绩比 $a_i$ 大的同学。

一个关键的观察是：为了让其他小组有最优的选择，当我们以 $a_i$ 为中位数时，应该选择那些“最没用”的同学作为搭档。但这里“没用”不好定义。一个更稳妥的想法是，我们只关心选了哪些人当了中位数，哪些人当了“小弟”（成绩比中位数小），哪些人当了“大哥”（成绩比中位数大）。

这听起来就像一个动态规划问题了！我们可以按排好序的成绩 a[0], a[1], ..., a[n-1] 依次处理每个学生，决定他们的“角色”。

DP状态设计

我们来设计一下 DP 状态。当我们处理到第 i 个学生（a[i]）时，我们需要知道哪些信息才能做出最优决策呢？我们需要知道：

到目前为止，我们已经确定了多少个小组的中位数了。
为了凑齐这些小组，我们总共需要多少对“小弟”和“大哥”。

于是，我们可以定义一个 DP 状态： dp[i][j][k] 表示：考虑了前 i 个学生（a[0] 到 a[i-1]），已经选定了 j 个学生作为中位数，这 j 个小组总共需要 k 对“小弟-大哥”组合（也就是总共需要 k 个“小弟”和 k 个“大哥”）。此时能获得的最大分值总和。

DP转移方程

当我们考虑第 i 个学生 a[i-1] 时，他有两种可能：

不当本组的中位数：他可以被留下来，等待之后成为某个更大中位数的“小弟”。在这种情况下，我们直接从上一个状态继承过来： dp[i][j][k] = dp[i-1][j][k]
当某个小组的中位数：假设 a[i-1] 是第 j 个中位数，他所在小组的大小为 $y = 2p+1$ (其中 $p$ 是该组需要的配对数)。那么这个决策是从一个“已经考虑了 i-1 个学生，选了 j-1 个中位数，总共需要 k-p 对配对”的状态转移过来的。 dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-p] + (a[i-1] ^ b_y))

这个转移需要对所有可能的组大小 $y$ （也就是所有可能的配对数 $p$ ）进行尝试。

约束条件

DP 的状态和转移必须满足一些约束条件，不然就乱套啦，喵~ 对于状态 dp[i][j][k]：

“小弟”的来源：这 j 个中位数都是从前 i 个学生中选的。他们需要的 k 个“小弟”，也必须从前 i 个学生中来。在前 i 个学生中，有 j 个当了中位数，剩下 i-j 个是非中位数。所以，我们必须有 k <= i-j，不然“小弟”都不够分！
“大哥”的来源：这 j 个中位数需要的 k 个“大哥”，必须从还没考虑的学生（即 a[i] 到 a[n-1]）中选。剩下的学生有 n-i 个，其中有 s-j 个将成为中位数，所以非中位数有 n-i-(s-j) 个。因此，我们必须有 k <= n-i-(s-j)，不然“大哥”也不够！

空间优化

上面的 dp[i][j][k] 是三维的，但我们发现 dp[i] 只依赖于 dp[i-1]。所以可以用滚动数组优化，把空间复杂度从 $O(N^3)$ 降到 $O(N^2)$ 。我们可以用 dp[j][k] 和 new_dp[j][k] 来交替计算。

整体算法流程

对学生成绩 a 数组进行排序。
处理一下输入的 b 数组和分组范围 [l, r]。因为小组人数 y 是奇数，可以写成 y = 2k+1，其中 k 是每组需要的配对数。l <= 2k+1 <= r 意味着 (l-1)/2 <= k <= (r-1)/2。我们计算出 k 的范围 [min_pairs, max_pairs]。
枚举小组的总数 s，从 1 到 n (步长为2，因为总人数 n 和小组数 s 的奇偶性必须相同)。
对于每个 s，进行一次 DP 计算： a. 初始化 dp 表，dp[0][0] = 0，其余为负无穷。 b. 循环 i 从 1 到 n (考虑学生 a[i-1])。 c. 循环 j 从 0 到 s (已定中位数数量)。 d. 循环 k 从 0 到 (n-s)/2 (总配对数)。 e. 执行 DP 转移，并检查约束条件。
DP结束后，dp[s][(n-s)/2] 就是分成 s 组能得到的最大总分。用它除以 s 得到平均分。
在所有可能的 s 中，找到最大的平均分。如果一次成功的DP都没有，说明无解。

这个 DP 的时间复杂度看起来是 $O(N \cdot S \cdot T \cdot \text{range}) \approx O(N^5)$ (其中 $S$ 是小组数, $T$ 是总配对数, range是每组配对数的范围)，对于 $N=80$ 来说非常高。但是，由于有严格的约束条件 (k <= i-j 等)，很多状态和转移都是无效的，实际运行起来会快很多，可以通过此题，喵~

代码实现

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

const long long INF = 1e18; // 使用一个足够大的数表示负无穷

int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    int l_raw, r_raw;
    std::cin >> n >> l_raw >> r_raw;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    // 为了方便处理中位数，先把成绩排序
    std::sort(a.begin(), a.end());

    // b_y 中的 y 是小组人数，是奇数。我们把它转换成按配对数 k 索引。
    // y = 2k+1, 所以 k = (y-1)/2。 b_y 对应 b_pairs[k]。
    std::vector<int> b_pairs(n / 2 + 1); 
    for (int i = 1; i <= n; ++i) {
        int val;
        std::cin >> val;
        if (i % 2 != 0) { // 只关心奇数大小的组
            b_pairs[(i - 1) / 2] = val;
        }
    }

    // 将组人数范围 [l, r] 转换为配对数范围 [min_pairs, max_pairs]
    // y = 2k+1, l <= y <= r -> (l-1)/2 <= k <= (r-1)/2
    int min_pairs = (l_raw - 1) / 2;
    int max_pairs = (r_raw - 1) / 2;

    // 如果最小的奇数都比 r_raw 大，或者 l_raw 是偶数时 l_raw+1 > r_raw
    if (l_raw > r_raw || (l_raw % 2 == 0 && l_raw + 1 > r_raw) ) {
        min_pairs = 1;
        max_pairs = 0;
    } else {
        if (l_raw % 2 == 0) min_pairs = (l_raw) / 2;
    }


    long long max_avg_score = -1;

    // 1. 枚举小组数量 s
    // n 和 s 的奇偶性必须相同，因为每个小组都是奇数人
    for (int s = (n % 2 == 0 ? 2 : 1); s <= n; s += 2) {
        if (s == 0) continue;
        int total_pairs = (n - s) / 2;

        // 检查分组是否可能
        if (s * l_raw > n || s * r_raw < n) {
            continue;
        }

        // 2. DP 求解最大总分
        // dp[j][k]: 选了 j 个中位数，总共需要 k 对配对的最大分数
        std::vector<std::vector<long long>> dp(s + 1, std::vector<long long>(total_pairs + 1, -INF));
        dp[0][0] = 0;

        // i: 考虑前 i 个学生 (a[0]...a[i-1])
        for (int i = 1; i <= n; ++i) {
            auto new_dp = dp; // 滚动数组
            // j: 已经定了 j 个中位数
            for (int j = 1; j <= s; ++j) {
                // k: 这 j 组总共需要 k 对 "小弟-大哥"
                for (int k = 0; k <= total_pairs; ++k) {
                    // 决策点：a[i-1] 是否作为第 j 个中位数
                    // p: a[i-1] 所在的小组需要 p 对配对
                    for (int p = min_pairs; p <= max_pairs; ++p) {
                        if (k >= p) {
                            // 约束条件检查
                            // 1. "小弟"来源: k个小弟需要从前i-1个非中位数里出, i-1个学生里有j-1个中位数, 剩下(i-1)-(j-1)=i-j个
                            bool condition1 = (k <= i - j);
                            // 2. "大哥"来源: k个大哥需要从后n-i个非中位数里出, n-i个学生里有s-j个中位数, 剩下n-i-(s-j)个
                            bool condition2 = (k <= n - i - (s - j));
                            
                            if (condition1 && condition2 && dp[j-1][k-p] > -INF) {
                                new_dp[j][k] = std::max(new_dp[j][k], dp[j - 1][k - p] + (a[i - 1] ^ b_pairs[p]));
                            }
                        }
                    }
                }
            }
            dp = new_dp;
        }
        
        if (dp[s][total_pairs] > -INF) {
            max_avg_score = std::max(max_avg_score, dp[s][total_pairs] / s);
        }
    }

    std::cout << max_avg_score << "\n";

    return 0;
}

复杂度分析

时间复杂度: $O(N \cdot S \cdot T \cdot P)$ ，其中 $N$ 是学生数， $S$ 是小组数， $T$ 是总配对数， $P$ 是单个小组的配对数范围。在最坏情况下， $S, T, P$ 都可以是 $O(N)$ 级别，所以理论上复杂度是 $O(N^5)$ 。但是，由于我们加了非常强的剪枝（状态的约束条件），很多 DP 状态和转移路径都是不可能的，这使得实际运行的计算量远小于理论上界，所以对于 $N=80$ 的数据范围是可以通过的，喵~
空间复杂度: $O(S \cdot T)$ 。我们使用了滚动数组，所以 DP 表的空间是二维的。 $S$ 和 $T$ 都是 $O(N)$ 级别，所以空间复杂度是 $O(N^2)$ 。

知识点总结

这道题是一道非常棒的组合优化问题，融合了多种算法思想：

问题转化: 将复杂的“最大化平均值”问题，通过枚举分母（小组数量 $s$ ），转化为更直接的“最大化总和”问题。
动态规划: 核心解法是 DP。状态设计是关键，需要准确捕捉解决问题所需的所有信息（已选的中位数数量、总配对需求）。
排序: 预处理阶段对成绩排序是解决中位数问题的标准操作，它使得问题的结构变得清晰。
约束与剪枝: DP 的效率严重依赖于有效的状态约束。正确分析并实现“小弟”和“大哥”来源的限制，是让高复杂度算法得以通过的关键。
滚动数组: 经典的 DP 空间优化技巧，当 dp[i] 只依赖于 dp[i-1] 时，就可以使用。

希望这篇题解能帮到你，喵~ 如果还有不懂的地方，随时可以再来问我哦！

分组（version 2） - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

DP状态设计 ​

DP转移方程 ​

约束条件 ​

空间优化 ​

整体算法流程 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​