题解：P11085 [ROI 2019] 学生座位 (Day 2)

joe_zxq · 2025-10-28 16:19:16 · 题解

首先，做这道题需要注意到下面的性质：

• 性质 1：同一个班中按身高排序，序号为 2i-1 的人和序号为 2i 个人一定用同一张桌子。
• 性质 2：不同班之间序号相同的人一定用同一张桌子。

这时候对于不同班中的同一张桌子，枚举使用哪一张桌子并计算代价找出最优解。时间复杂度：\mathcal O(NMK)，期望得分 70。

我们考虑优化掉这个对于选择桌子的枚举，注意到下面的决策单调性：

• 序号更小的人一定用范围左端点一样或更小的桌子。

时间复杂度：\mathcal O(K \log N \log M)。

:::info[正解代码]

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll N = 2e5 + 5;
ll m, n, k, ans, l[N], r[N];
vector<ll> a[N], h[N], pre[N];
map<ll, ll> mx;

ll sum(ll i, ll l, ll r) {
    return pre[i][r] - pre[i][l - 1];
}

ll calc(ll i, ll l, ll r) {
    ll x = lower_bound(h[i].begin(), h[i].end(), l) - h[i].begin() - 1;
    ll y = upper_bound(h[i].begin(), h[i].end(), r) - h[i].begin();
    return x * l - sum(i, 1ll, x) + sum(i, y, 2 * m) - (2 * m - y + 1) * r;
}

void solve(ll ql, ll qr, ll al, ll ar) {
    if (ql > qr) { return; }
    ll cur = (ql + qr) >> 1;
    ll res = 1e18, id = -1;
    for (ll i = al; i <= ar; i++) {
        ll o = calc(cur, l[i], r[i]);
        if (o < res) {
            res = o;
            id = i;
        }
    }
    ans += res;
    solve(ql, cur - 1, al, id);
    solve(cur + 1, qr, id, ar);
}

void solve() {
    scanf("%lld %lld %lld", &m, &n, &k);
    for (ll i = 1; i <= k; i++) {
        scanf("%lld %lld", &l[i], &r[i]);
        mx[l[i]] = max(mx[l[i]], r[i]);
    }
    ll tot = 0;
    for (auto p : mx) {
        tot++;
        l[tot] = p.first, r[tot] = p.second;
    }
    k = tot;
    for (ll i = 1; i <= m; i++) {
        a[i].push_back(0ll);
        for (ll j = 1, x; j <= 2 * n; j++) {
            scanf("%lld", &x);
            a[i].push_back(x);
        }
        stable_sort(a[i].begin(), a[i].end());
    }
    for (ll i = 1; i <= n; i++) {
        h[i].push_back(0ll);
        for (ll j = 1; j <= m; j++) {
            h[i].push_back(a[j][i * 2 - 1]);
            h[i].push_back(a[j][i * 2]);
        }
        stable_sort(h[i].begin(), h[i].end());
        pre[i].push_back(0ll);
        for (ll j = 1; j <= 2 * m; j++) {
            pre[i].push_back(pre[i].back() + h[i][j]);
        }
    }
    solve(1ll, n, 1ll, k);
    printf("%lld\n", ans);
}

int main() {
    solve();
    return 0;
}

:::