消失吧，群青

发现时刻和位置可以非整数很难处理，由于精度要求不高，我们把时间和长度尺度全部乘以

10^k

，只考虑在整数情况，最后把答案除以

10^k

，这样数值上能近似求出在任意时刻都可以转弯的答案，这里

k

取

3

足够了。

二分答案

d

。把流星按照时间排序。发现每个时刻能到达的点集是一些区间的并，我们用一个 set 维护这些区间，时间经过

t

会让这些区间的左右端点各延伸

t

单位长度，并合并相邻有交的区间，在坐标

x

上落下流星等于该时刻不能位于

[x-d+1,x+d-1]

，需要点集内在该区间内的点删除。删除操作就类似 ODT 直接可以做完，每次暴力延伸区间时间复杂度不可行，所以我们给每个区间再带上一个标记表示上次被更新的时刻，删除操作只关心和

[x-d+1,x+d-1]

有交的区间，我们只更新左右端点前后的区间即可。然后做完了，复杂度

O(n\log n\log V)

。

CPP

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 2e5 + 10;
int n; pair<LL, LL> A[N];

struct Info { LL l, r, t; };
const bool operator<(const Info a, const Info b) {
	return (a.l != b.l ? a.l < b.l : (a.r != b.r ? a.r < b.r : a.t < b.t));
}
set<Info> s;
void upd(Info x, LL t) {
	auto it = s.find(x);
	if (it == s.end()) return ;
	auto [l, r, t0] = *it; r += t - t0; l -= t - t0; it = s.erase(it);
	while (it != s.end() && it->l - r <= t - it->t)
		r = max(r, it->r + t - it->t), it = s.erase(it);
	while (it != s.begin()) {
		it = prev(it); if (l - it->r > t - it->t) break;
		l = min(l, it->l - t + it->t); it = s.erase(it);
	}
	s.insert({l, r, t});
}
void upd(LL x, LL t) {
	auto it = s.lower_bound({x + 1, 0, 0}); upd(*it, t);
	it = s.lower_bound({x + 1, 0, 0}); if (it != s.begin()) upd(*prev(it), t);
}
bool check(LL d) {
	if (d == 0) return true;
	s.clear(); s.insert({0, 0, 0});
	for (int i = 1; i <= n; i ++) {
		if (s.empty()) return false;
		auto [cur, x] = A[i];
		LL l = x - d + 1, r = x + d - 1;
		upd(r, cur); upd(l, cur);  
		auto it = s.lower_bound({l + 1, 0, 0}); 
		if (it != s.begin() && prev(it)->r >= l) {
			auto [a, b, c] = *prev(it); s.erase(prev(it));
			if (a < l) s.insert({a, l - 1, c});
			if (b > r) { s.insert({r + 1, b, c}); continue; }
		}
		while (it != s.end() && it->l <= r) {
			auto [a, b, c] = *it; it = s.erase(it);
			if (b > r) { s.insert({r + 1, b, c}); break; }
		}
	}
	return !s.empty();
}

int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	cin >> n; const ull K = 1000;
	for (int i = 1, t, x; i <= n; i ++)
		cin >> t >> x, A[i] = {1ll * t * K, 1ll * x * K};
	sort(A + 1, A + 1 + n);
	LL L = 0, R = 1e13;
	while (L + 1 < R) {
		LL mid = (L + R) >> 1;
		if (check(mid)) L = mid;
		else R = mid;
	}
	cout << fixed << setprecision(1) << (double)L / K << "\n";
	return 0;
}

文章操作

相关推荐

评论

消失吧，群青