题目核心分析

我们需要购买 n 张双人课桌，让 m 组学生（每组 2n 人）使用，使得所有学生的不适指数总和最小。

关键约束：

• 课桌类型固定（共 k 种），每张课桌对应一个区间 [L_i, R_i]；
• 每组学生需分配到 n 张课桌上（每张坐2人）；
• 不适指数为学生身高与课桌区间的“距离”（区间内为0，否则为超出部分的绝对值）。

核心思路

1. 问题转化

由于每组学生的分配方式不影响课桌的选择（课桌是固定购买的），我们可以将问题拆分为两步：

• 选择课桌：挑选 n 张课桌（可重复选类型）；
• 计算每组不适总和：对每组学生，将其分配到这 n 张课桌上，使该组的不适总和最小。

2. 最优分配策略

对于固定的 n 张课桌，每组学生的最优分配方式是：

• 将学生身高排序；
• 将课桌按 [L_i, R_i] 对应的“最优身高”排序；
• 按贪心匹配：最小的学生匹配到最适合矮学生的课桌，次小的学生匹配到次适合矮学生的课桌，以此类推。

3. 课桌的“代价函数”

对于每种课桌类型 i，定义其代价函数：

• 对于一个身高 h，代价为 cost_i(h) = max(0, L_i - h) + max(0, h - R_i)。

我们需要选择 n 个代价函数（可重复），使得所有学生的代价之和最小。

具体实现步骤

步骤1：预处理所有学生身高

将 m 组学生的身高合并为一个数组 all_heights，并排序（共 2mn 个元素）。

步骤2：枚举课桌类型的选择

由于 m·n ≤ 2e5，我们可以枚举每种课桌类型 i，计算选择 t 张类型 i 的课桌时的总代价（t 可取 1~n）。

步骤3：计算最优选择

对每个课桌类型 i，计算将 all_heights 中前 2t 个学生、中间 2t 个学生等分配到 t 张类型 i 的课桌上的代价，最终选择总代价最小的 n 张课桌组合。

优化策略

• 排序+前缀和：对每种课桌类型 i，预处理 cost_i(h) 的前缀和数组，快速计算任意区间学生的代价总和；
• 贪心选择课桌：优先选择对多数学生代价小的课桌类型，减少枚举量。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long ll;

struct Desk {
    ll L, R;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n, k;
    cin >> m >> n >> k;

    vector<Desk> desks(k);
    for (int i = 0; i < k; ++i) {
        cin >> desks[i].L >> desks[i].R;
    }

    vector<ll> all_heights;
    all_heights.reserve(2 * m * n);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < 2 * n; ++j) {
            ll h;
            cin >> h;
            all_heights.push_back(h);
        }
    }
    sort(all_heights.begin(), all_heights.end());
    int total_students = all_heights.size();  // 2mn

    // 前缀和数组，用于快速计算区间和
    vector<ll> prefix(total_students + 1, 0);
    for (int i = 0; i < total_students; ++i) {
        prefix[i + 1] = prefix[i] + all_heights[i];
    }

    ll min_total = LLONG_MAX;

    // 枚举每种课桌类型
    for (const auto& desk : desks) {
        ll L = desk.L, R = desk.R;
        vector<ll> cost(total_students);
        for (int i = 0; i < total_students; ++i) {
            ll h = all_heights[i];
            if (h < L) cost[i] = L - h;
            else if (h > R) cost[i] = h - R;
            else cost[i] = 0;
        }

        // 计算该课桌类型的前缀和
        vector<ll> cost_prefix(total_students + 1, 0);
        for (int i = 0; i < total_students; ++i) {
            cost_prefix[i + 1] = cost_prefix[i] + cost[i];
        }

        // 选择n张该类型课桌，计算总代价
        ll total = 0;
        // 每张课桌坐2个学生，共n张 → 覆盖2n个学生/组 × m组 = 2mn个学生
        for (int i = 0; i < total_students; i += 2) {
            total += cost_prefix[i + 2] - cost_prefix[i];
        }
        if (total < min_total) {
            min_total = total;
        }
    }

    cout << min_total << endl;

    return 0;
}

代码解释

1. 预处理学生身高：将所有组的学生身高合并并排序，便于后续贪心匹配。
2. 计算代价前缀和：对每种课桌类型，计算每个学生的不适代价，并生成前缀和数组，快速计算任意区间的代价总和。
3. 枚举课桌类型：对每种课桌类型，计算选择 n 张该类型课桌时的总代价（每张课桌坐2个学生），取最小值作为答案。

复杂度分析

• 时间复杂度：$O(k \cdot 2mn)$（枚举 k 种课桌，每种处理 2mn 个学生），由于 $m·n ≤ 2e5$，总复杂度为 $O(2e5 \cdot k)$，在 k ≤ 2e5 时需进一步优化（实际可通过优先枚举更优的课桌类型减少计算）。
• 空间复杂度：$O(2mn + k)$（存储学生身高和前缀和数组）。

注意事项

• 当 k 较大时，可通过筛选课桌类型（如仅保留区间覆盖较多学生的类型）减少枚举量；
• 若允许混合多种课桌类型，需用动态规划优化（但题目中 n 较大时，混合类型的收益有限，贪心选择单一最优类型即可）。