专栏文章

题解：P13532 [OOI 2023] Buying gifts / 购买礼物

ccjrqwq
P13532题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio0hzar
此快照首次捕获于
2025/12/02 11:21
3 个月前
此快照最后确认于
2025/12/02 11:21
3 个月前
查看原文
我们考虑固定 aa 的最大值，来通过某些数据结构维护 bb。
把 aa 从小到大排序，遍历。设当前的最大值为 axa_x。那比 axa_x 小的 aia_i 的选择是可以选 aia_i，也可以选 bib_i，选 aia_i 对答案无影响，bib_i 会影响答案，所以我们要尝试使用 bib_i 更新答案。比 xx 大的 aja_j 是必须选择 bjb_j，否则与固定 axa_x 矛盾。
所以对于 ii 需要维护 bb 中的前驱，后继。对于 jj 需要维护 bb 中的最大值。
具体而言，对于 ii，我们使用 std::set。找到与 axa_x 在数轴上最近的 bib_i。 对于 jj。我们可以使用线段树（单点修改，查询全局最大），或者优先队列（每次标记 xx 失效，查询第一个有效的最大值）。
时间复杂度 O(nlog⁡n)O(n\log n)。
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 2e5+10;
int n,a[N],b[N];

struct Node{
	int val,ma;
}c[N<<2];
#define mid (l+r)/2
#define ls (u*2)
#define rs (u*2+1)
void pushup(int u) {
	c[u].ma = max(c[ls].ma, c[rs].ma);
}
void build(int u,int l,int r) {
	if (l == r) {
		c[u].val = c[u].ma = b[l];
		return ;
	}
	build(ls,l,mid), build(rs,mid+1,r);
	pushup(u);
}
void upd(int u,int l,int r,int x,int v) {
	if (l == r) {
		c[u].val = c[u].ma = v;
		return ;
	}
	if (x <= mid) upd(ls,l,mid,x,v);
	else upd(rs,mid+1,r,x,v);
	pushup(u);
}
int mp[N];
void slove() {
	cin>>n;
	set<int>s;
	for (int i=1;i<=n;i++) {
		cin>>a[i]>>b[i];
	}
	build(1,1,n);
	iota(mp+1,mp+n+1,1);
	sort(mp+1,mp+n+1,[](int x,int y) {
		return a[x] < a[y];
	});
	int mxA = 0, ans = 2e9;
	for (int i=1;i<=n;i++) {
		mxA = a[mp[i]];
		upd(1,1,n,mp[i],0);
		auto it = s.lower_bound(mxA);
		if (it != s.end()) {
			int x = *it;
			if (x > c[1].ma) {
				ans = min(ans, abs(mxA - x));
			}
		}
		if (it != s.begin()) {
			int x = *prev(it);
			if (x > c[1].ma) {
				ans = min(ans, abs(mxA - x));
			}
		}
		ans = min(ans, abs(mxA - c[1].ma));
		s.insert(b[mp[i]]);
	}
	cout << ans << '\n';
}
int main() {
	cin.tie(nullptr) -> sync_with_stdio(false);
	int T=1;
	while(T--) {
		slove();
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...