本题的核心在于利用单调性优化分配策略，从而降低时间复杂度。

问题描述

给定若干课桌和学生，每张课桌有一个范围 [l, r] 表示可以容纳的学生高度范围。需要将学生分配到课桌上，使得总不适值最小化。

解题思路

首先，我们可以通过排除那些完全无用的课桌（即被其他课桌完全覆盖的范围）来减少计算量。

接着，假设我们已经选定了某些课桌，并按照左端点排序。那么对于每个学生组，应该按照高度从低到高依次安排到这些课桌上。

我们可以重新定义问题：不再考虑分组，而是直接将同一张课桌上的学生视为一组，这样共有 2m 组学生。然后对这 2m 组学生进行分治处理，利用课桌的单调性递归求解左右子问题。

算法实现

以下是两种实现方式：

非精细实现

#include 
using namespace std;

typedef long long LL;
const int MAXN = 200005;
int m, n, k;
bool tag[MAXN];
struct Table {
    int l, r;
} tbs[MAXN];

LL calc(LL s_l, LL s_r, LL tbl) {
    LL res = 0;
    if (s_l < tbl.l) res += tbl.l - s_l;
    if (s_l > tbl.r) res += s_l - tbl.r;
    if (s_r < tbl.l) res += tbl.l - s_r;
    if (s_r > tbl.r) res += s_r - tbl.r;
    return res;
}

LL divide(int st, int ed, int tbl_s, int tbl_e) {
    if (st > ed) return 0;
    LL ret = 0;
    if (tbl_s == tbl_e) {
        for (int i = 1; i <= m; ++i)
            for (int j = st; j <= ed; ++j)
                ret += calc(tbs[j].l, tbs[j].r, tbs[tbl_s]);
        return ret;
    }
    int mid = (st + ed) / 2, best = tbl_s;
    LL min_cost = LLONG_MAX;
    for (int i = tbl_s; i <= tbl_e; ++i) {
        LL tmp = 0;
        for (int j = 1; j <= m; ++j)
            tmp += calc(tbs[mid].l, tbs[mid].r, tbs[i]);
        if (tmp < min_cost) {
            min_cost = tmp;
            best = i;
        }
    }
    return min_cost + divide(st, mid - 1, tbl_s, best) + divide(mid + 1, ed, best, tbl_e);
}

int main() {
    cin >> m >> n >> k;
    for (int i = 1; i <= k; ++i) cin >> tbs[i].l >> tbs[i].r;
    sort(tbs + 1, tbs + k + 1, [&](Table a, Table b) -> bool {
        if (a.l != b.l) return a.l < b.l;
        return a.r > b.r;
    });
    // 去重
    int cnt = 0;
    for (int i = 1; i <= k; ++i) {
        if (cnt && tbs[cnt].l <= tbs[i].l && tbs[cnt].r >= tbs[i].r) continue;
        tbs[++cnt] = tbs[i];
    }
    k = cnt;
    cout << divide(1, n, 1, k) << endl;
    return 0;
}

精细实现

#include 
using namespace std;

typedef long long LL;
const int MAXN = 200005;
int m, n, k;
bool tag[MAXN];
struct Table {
    int l, r;
} tbs[MAXN];

LL get_cost(int h, Table &t) {
    if (h < t.l) return t.l - h;
    if (h > t.r) return h - t.r;
    return 0;
}

LL prefix_sum[2 * MAXN];
LL query(int l, int r) {
    if (l > r) return 0;
    return prefix_sum[r] - (l ? prefix_sum[l - 1] : 0);
}

LL solve(int st, int ed, int tbl_st, int tbl_ed) {
    if (st > ed) return 0;
    int mid = (st + ed) / 2, opt = tbl_st;
    LL min_val = LLONG_MAX;
    // 计算前缀和
    for (int i = 0; i < 2 * m; ++i) prefix_sum[i] = (i ? prefix_sum[i - 1] : 0) + sorted_students[mid][i];
    for (int i = tbl_st; i <= tbl_ed; ++i) {
        int less = 0, more = 0;
        while (less < 2 * m && sorted_students[mid][less] < tbs[i].l) ++less;
        while (more < 2 * m && sorted_students[mid][more] <= tbs[i].r) ++more;
        LL cost = 1LL * tbs[i].l * less - query(0, less - 1) + query(more, 2 * m - 1) - 1LL * (2 * m - more) * tbs[i].r;
        if (cost < min_val) {
            min_val = cost;
            opt = i;
        }
    }
    return min_val + solve(st, mid - 1, tbl_st, opt) + solve(mid + 1, ed, opt, tbl_ed);
}

int main() {
    cin >> m >> n >> k;
    for (int i = 1; i <= k; ++i) cin >> tbs[i].l >> tbs[i].r;
    sort(tbs + 1, tbs + k + 1, [&](Table a, Table b) -> bool {
        if (a.l != b.l) return a.l < b.l;
        return a.r > b.r;
    });
    int unique = 0;
    for (int i = 1; i <= k; ++i) {
        if (unique && tbs[unique].l <= tbs[i].l && tbs[unique].r >= tbs[i].r) continue;
        tbs[++unique] = tbs[i];
    }
    k = unique;
    vector sorted_students(n, vector<int>());
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < 2 * n; ++j) cin >> heights[j];
        sort(heights, heights + 2 * n);
        for (int j = 0; j < 2 * n; j += 2) {
            sorted_students[j / 2].push_back(heights[j]);
            sorted_students[j / 2].push_back(heights[j + 1]);
        }
    }
    for (int i = 0; i < n; ++i) sort(sorted_students[i].begin(), sorted_students[i].end());
    cout << solve(0, n - 1, 1, k) << endl;
    return 0;
}

时间复杂度

该算法的时间复杂度为 O((k + nm) log n)，其中 k 是课桌数量，n 是学生组数，m 是每组学生的数量。