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

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

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

这时候对于不同班中的同一张桌子，枚举使用哪一张桌子并计算代价找出最优解。时间复杂度：

\mathcal O(NMK)

，期望得分

70

。

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

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

时间复杂度：

\mathcal O(K \log N \log M)

。

正解代码

CPP

#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;
}

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

文章操作

相关推荐

评论

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