分组（version 1） - 题解

标签与难度

标签: 贪心, 数学, 构造, 前缀和, 思维题, 动态规划难度: 2200

题目大意喵~

主人你好呀，喵~ 🐾 这里有一道关于分组的有趣问题哦！

我们有 $n$ 个学生，每个学生都有一个成绩 $a_i$ 。现在要把他们分成好多个小组，但是有几个规矩要遵守哦：

每个小组的人数都必须是奇数。
每个小组的人数 $y$ 必须在 $[l, r]$ 这个区间里。
一个小组的“分值”，就是这个小组里所有人按成绩排好序后，排在最中间那个同学的成绩（也就是中位数啦！）。
一个分组方案的总分，是所有小组分值的 平均数。

我们的任务，就是找到一个分组方案，让这个平均分最大！最后输出这个最大平均分向下取整的结果。如果不存在任何可行的分组方案，就告诉人家 "-1" 哦。

举个栗子：如果一个小组有5个同学，成绩是 {10, 20, 50, 30, 40}，排好序就是 {10, 20, 30, 40, 50}，那么这个小组的分值就是 30 啦！

（偷偷告诉你，题目里提到的 $b_y$ 好像是迷惑你的烟雾弹，实际解题中用不到它哦，喵~）

解题思路分析

这道题的目标是最大化 (所有小组的中位数之和) / (小组的数量)。这是一个分数规划问题的经典形式，不过直接用分数规划（比如二分答案）可能会很复杂，而且对于这道题的数据范围来说太慢了。所以我们得找找有没有更巧妙的办法，喵！

关键的第一步：排序！

要想让中位数的和最大，我们肯定希望那些成绩最高的同学能成为中位数，对吧？所以，一个非常自然的想法就是先把所有学生的成绩 $a_i$ 从大到小排个序。这样一来，成绩最高的学生们就排在数组的最前面啦。

排序后，我们得到一个新的成绩数组 a，其中 $a_0 \ge a_1 \ge a_2 \ge \dots \ge a_{n-1}$ 。

第二步：中位数和分组的关系

如果我们把排好序的学生们分成几个 连续的 区段，每个区段作为一个小组，这样做是不是最优的呢？答案是肯定的，喵！如果不这么做，比如我们把 $a_i$ 和 $a_k$ 交换一下位置（其中 $i < k$ ），那么原来可能成为中位数的某个 $a_j$ ( $j<k$ )，现在可能会被一个更小的分数替换，总分肯定不会变得更优。所以，最优解一定是通过将排序后的学生序列划分成若干连续的块得到的。

一个大小为 $y$ （奇数）的小组，它的中位数是这个小组里排在第 $(y+1)/2$ 位的同学。如果我们把 $a_0, \dots, a_{y-1}$ 这 $y$ 个同学分成一组，那么中位数就是 $a_{(y-1)/2}$ 。如果我们接着把 $a_y, \dots, a_{y+y'-1}$ 这 $y'$ 个同学分成一组，那么中位数就是 $a_{y + (y'-1)/2}$ 。

第三步：确定分组策略

现在问题变成了：如何把长为 $n$ 的有序序列 a 切分成若干段，每段长度 $y_j$ 都是 $[l, r]$ 范围内的奇数，并且所有段的中位数之和除以段数最大？

我们来分析一下，对于一个固定的分组数量 $k$ ：

我们需要将 $n$ 个学生分成 $k$ 组。
设每组大小为 $y_1, y_2, \dots, y_k$ 。则 $\sum y_j = n$ ，且 $l \le y_j \le r$ ， $y_j$ 为奇数。
中位数之和为 $S = a_{(y_1-1)/2} + a_{y_1 + (y_2-1)/2} + \dots$
为了让 $S$ 最大，我们希望中位数的下标尽可能小。
中位数 $a_{\text{index}}$ 的下标 index 取决于它前面有多少个小组，以及这些小组的大小。具体来说，第 $j$ 个小组的中位数下标是 $\sum_{i=1}^{j-1} y_i + (y_j-1)/2$ 。
为了让所有下标都尽可能小，我们应该把 尺寸较小 的组放在前面。

这引出了一个非常重要的猜想（也是本题的解题关键！）：对于一个固定的分组数 $k$ ，要使中位数之和最大，最优的策略是只使用尺寸为 $l$ 和 $r$ (即区间端点) 的小组。

为什么呢？这有点像一个“凸性”问题。如果我们有一个中间大小的小组（比如 $l+2$ ），我们通常可以把它调整成一个 $l$ 的小组和一个 $r$ 的小组（或者反之），通过把“资源”推向两端，往往能获得更优的解。虽然严格证明有点复杂，但在比赛中，这是一个非常有效的直觉和猜想！

第四步：枚举分组数 $k$

有了上面的猜想，问题就变得清晰多啦！我们可以枚举所有可能的分组数量 $k$ 。一个合法的 $k$ 需要满足什么条件呢？

奇偶性：因为每个小组人数 $y_j$ 都是奇数，所以 $n = \sum y_j$ 的奇偶性必须和 $k$ （小组个数）的奇偶性相同。也就是说，n % 2 == k % 2。
人数限制：如果全用最小的组，总人数是 $k \times l$ ；如果全用最大的组，总人数是 $k \times r$ 。所以必须满足 $k \times l \le n \le k \times r$ 。

对于每个满足条件的 $k$ ，我们假设它是由 $c_l$ 个大小为 $l$ 的组和 $c_r$ 个大小为 $r$ 的组构成的。我们可以列出方程组：

\begin{cases} c_l + c_r = k \\ c_l \cdot l + c_r \cdot r = n \end{cases}

解这个方程组，我们可以得到：

c_r = \frac{n - k \cdot l}{r - l}

c_l = k - c_r

如果解出来的 $c_l$ 和 $c_r$ 都是非负整数，那么这个 $k$ 就是一个可行的分组方案！

第五步：快速计算中位数之和

对于一个可行的 $(k, c_l, c_r)$ 方案，我们把 $c_l$ 个大小为 $l$ 的组放在前面， $c_r$ 个大小为 $r$ 的组放在后面，这样能让中位数的下标最小化。中位数之和就是：

\text{Sum} = \left( \sum_{i=0}^{c_l-1} a_{i \cdot l + \frac{l-1}{2}} \right) + \left( \sum_{j=0}^{c_r-1} a_{c_l \cdot l + j \cdot r + \frac{r-1}{2}} \right)

这个式子是在两个不同的算术级数上求和。如果每次都循环计算，总时间复杂度会是 $O(N^2/L)$ 级别，还是太慢了。

我们可以用 前缀和 来优化！不过不是普通的前缀和，而是 基于算术级数的前缀和。

对步长为 $l$ 的所有算术级数，我们都预处理出前缀和。具体来说，对于每个余数 rem from 0 to l-1，我们把所有下标 idx 满足 idx % l == rem 的 a[idx] 拿出来，单独计算它们的前缀和。
对步长为 $r$ 也做同样的事情。

这样预处理之后，我们就可以在 $O(1)$ 的时间内查到任何一段算术级数的和啦！

最终算法流程

把学生成绩从大到小排序。
处理一下 $l$ 和 $r$ ，让它们都变成奇数（如果 $l$ 是偶数就 l++，如果 $r$ 是偶数就 r--）。如果处理后 $l > r$ ，无解。
对步长为 $l$ 和 $r$ 的所有算术级数，预处理前缀和。
枚举所有可能的分组数 $k$ （注意奇偶性和人数限制）。
对于每个 $k$ ，计算出需要的 $l$ -尺寸组数 $c_l$ 和 $r$ -尺寸组数 $c_r$ 。
如果 $c_l, c_r$ 合法，利用预处理好的前缀和，在 $O(1)$ 时间内计算出总的中位数之和。
更新最大平均分。
最后输出结果，喵~

这个算法的预处理是 $O(N)$ ，枚举 $k$ 的循环次数大约是 $O(N/L)$ ，每次循环内部是 $O(1)$ ，所以总的时间复杂度是 $O(N)$ ，完全可以接受！

代码实现

这是我根据上面的思路，精心为你准备的代码哦~ 每一步都有详细的注释，希望能帮到你，喵！

cpp

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

// 一个辅助函数，用于查询算术级数上的区间和
// pref_sums: 预处理好的前缀和二维数组
// start_idx: 算术级数在原数组 a 中的起始下标
// step: 算术级数的步长
// count: 需要求和的项数
long long get_ap_sum(const std::vector<std::vector<long long>>& pref_sums, int start_idx, int step, int count) {
    if (count <= 0) {
        return 0;
    }
    int remainder = start_idx % step;
    int start_term_idx = start_idx / step;
    
    long long total_sum = pref_sums[remainder][start_term_idx + count - 1];
    if (start_term_idx > 0) {
        total_sum -= pref_sums[remainder][start_term_idx - 1];
    }
    return total_sum;
}

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

    int n;
    long long l, r;
    std::cin >> n >> l >> r;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    // 题目里的 b 数组是迷惑项，我们不需要读入它

    // 1. 从大到小排序，让成绩好的同学排在前面
    std::sort(a.begin(), a.end(), std::greater<int>());

    // 2. 保证 l 和 r 都是奇数
    if (l % 2 == 0) l++;
    if (r % 2 == 0) r--;

    if (l > r) {
        std::cout << -1 << std::endl;
        return 0;
    }

    // 3. 预处理算术级数前缀和
    // 对步长为 l 的情况
    std::vector<std::vector<long long>> pref_l(l);
    for (int i = 0; i < n; ++i) {
        pref_l[i % l].push_back(a[i]);
    }
    for (int i = 0; i < l; ++i) {
        for (size_t j = 1; j < pref_l[i].size(); ++j) {
            pref_l[i][j] += pref_l[i][j - 1];
        }
    }

    // 对步长为 r 的情况
    std::vector<std::vector<long long>> pref_r(r);
    if (l != r) {
        for (int i = 0; i < n; ++i) {
            pref_r[i % r].push_back(a[i]);
        }
        for (int i = 0; i < r; ++i) {
            for (size_t j = 1; j < pref_r[i].size(); ++j) {
                pref_r[i][j] += pref_r[i][j - 1];
            }
        }
    }

    long long max_avg = -1;

    // 4. 枚举所有可能的分组数 k
    long long min_k = (n + r - 1) / r;
    long long max_k = n / l;

    for (long long k = min_k; k <= max_k; ++k) {
        // 检查奇偶性
        if (k % 2 != n % 2) {
            continue;
        }

        long long cl = 0, cr = 0;

        // 5. 解方程计算 cl 和 cr
        if (l == r) {
            if (n == k * l) {
                cl = k;
                cr = 0;
            } else {
                continue;
            }
        } else {
            long long numerator = n - k * l;
            long long denominator = r - l;
            if (numerator % denominator != 0) {
                continue;
            }
            cr = numerator / denominator;
            cl = k - cr;
            if (cl < 0 || cr < 0) { // cl 应该不会小于0，但 cr 可能
                continue;
            }
        }
        
        // 6. 计算中位数之和
        long long current_sum = 0;
        long long ml = (l + 1) / 2;
        long long mr = (r + 1) / 2;

        // 计算 l-尺寸组的中位数之和
        current_sum += get_ap_sum(pref_l, ml - 1, l, cl);

        // 计算 r-尺寸组的中位数之和
        long long r_group_offset = cl * l;
        current_sum += get_ap_sum(pref_r, r_group_offset + mr - 1, r, cr);

        // 7. 更新最大平均分
        if (k > 0) {
            max_avg = std::max(max_avg, current_sum / k);
        }
    }

    std::cout << max_avg << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N + (N/L))$
- 排序需要 $O(N \log N)$ 的时间。
- 预处理前缀和：我们需要遍历一遍数组 a 来填充 pref_l 和 pref_r 的初始值，这需要 $O(N)$ 。然后对每个余数类别计算前缀和，总共也是 $O(N)$ 。所以预处理是 $O(N)$ 。
- 主循环：我们枚举分组数 $k$ 。 $k$ 的范围是从 $\lceil n/r \rceil$ 到 $\lfloor n/l \rfloor$ 。循环内部的所有操作都是 $O(1)$ 。在最坏情况下，这个循环的次数是 $O(N/L)$ 级别的。
- 所以总的时间复杂度瓶颈在于排序，为 $O(N \log N)$ 。如果使用计数排序等线性排序（如果成绩范围允许），则可以达到 $O(N)$ 。对于本题的通用整数， $O(N \log N)$ 是标准的。
空间复杂度: $O(N)$
- 我们需要存储排序后的数组 a，空间为 $O(N)$ 。
- 预处理的前缀和数组 pref_l 和 pref_r，它们存储的元素总数都是 $N$ 个，所以空间复杂度是 $O(N)$ 。

知识点总结

这道题真是一次有趣的冒险，不是吗？我们来总结一下这次探险中学到的武功秘籍吧，喵~

贪心思想: 面对 "最大化/最小化" 问题时，首先想到的就是贪心！将学生按成绩排序，优先让成绩高的人当上中位数，是解题的第一步。
问题转化: 成功地将一个复杂的分组问题，转化为了一个在有序序列上切块的问题，并进一步大胆猜想可以简化为只用两种尺寸的块来组合。这是解开难题的钥匙！
构造解: 对于固定的分组数 $k$ ，我们通过解线性方程组的方式，构造出了使用 $l$ -尺寸和 $r$ -尺寸小组的具体数量。
算术级数前缀和: 这是一个非常实用的技巧！当需要反复查询一个数组上等差数列位置元素的和时，可以预处理这些等差数列的前缀和，将每次查询的时间从 $O(\text{length})$ 优化到 $O(1)$ 。
枚举与剪枝: 通过分析题目性质（奇偶性、人数范围），我们确定了需要枚举的变量（分组数 $k$ ）的范围和条件，避免了无效的搜索。

希望这篇题解能让你有所收获！如果还有不明白的地方，随时可以再来问我哦！一起加油，变得更强，喵~ 💖

分组（version 1） - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键的第一步：排序！ ​

第二步：中位数和分组的关系 ​

第三步：确定分组策略 ​

第四步：枚举分组数 kkk ​

第五步：快速计算中位数之和 ​

最终算法流程 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​