526互联

Educational Codeforces Round 143 (Rated for Div. 2) B. Ideal Point

发布时间 2023-09-05 21:22:53作者: zsxuan

给 \(n\) 条一维线段，一条端点为 \(l, r\) 的线段可以覆盖 \(\forall i, l \leq i \leq r\) 。定义 \(f(x)\) 为点 \(x\) 被线段覆盖的次数。一个点 \(x\) 称为是 “完美的” 如果 \(y \neq x, f(x) > f(y)\) 。

给一个点 \(k\) ，询问是否能通过删除若干条线段使点 \(k\) 变为完美的。

观察一：所以没覆盖到 \(k\) 的线段的存在没有无意义，所以全部删除。

  • 哪怕不删除，也要判断当前线段是否覆盖到了 \(k\) ，这增加了工作。

观察二：剩下所有能覆盖到 \(k\) 的线段存在一个非空交集，交集中至少有 \(k\) 。

  • 剩下的线段交集为空则 \(k\) 无法被覆盖。

观察三：此时再删除线段只会使交集变大，而不会变小。

若余下剩下线段的交集大小为 \(1\) ，则存在使得 \(k\) 变为完美的方案。否则不存在。

view 
#include <bits/stdc++.h>
void solve() {
	int n, k; std::cin >> n >> k;
	std::vector<std::pair<int,int>> segs;
	for (int i = 0; i < n; i++) {
		int l, r; std::cin >> l >> r;
		if (l <= k && r >= k) segs.push_back({l,r});
	}
	int L = -1, R = 1 << 30;
	for (auto u : segs) {
		int l = u.first, r = u.second;
		L = std::max(L, l);
		R = std::min(R, r);
	}
	std::cout << (L == R ? "YES" : "NO") << '\n';
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}