小编点评

这个问题可以通过以下步骤解决： 1. **理解问题**：首先，仔细阅读题目描述，理解问题的背景和要求。 2. **分析解题思路**：观察问题，尝试找到可能的解题策略。在这个问题中，关键点在于理解贝西行走路线的限制条件和如何在给定的时间内访问尽可能多的地标。 3. **设计算法**：根据解题思路，设计具体的算法。在这个问题中，使用了二分法来寻找在给定时间内能访问的地标数量的最优解。同时，需要设计一个`check`函数来判断在当前猜测的数量下，是否能满足条件。 4. **实现算法**：将设计好的算法用代码实现，这是解决这个问题的关键步骤。在这个问题中，使用了C++编程语言，并利用了标准库中的`sort`函数来排序坐标。 5. **测试和调试**：最后，通过测试和调试来检验代码的正确性和效率。在这个问题中，需要进行充分的测试，包括不同的数据输入和边界情况，以确保代码能够在各种情况下都能正确运行。 6. **编写输出**：根据题目要求，编写正确的输出格式。 总结来说，这个问题主要考察了解决问题的能力、算法设计能力和编码能力。通过逐步理解和应用上述解题策略，可以正确解决这个问题。

正文

\(\color{black}\text{P2390 地标访问 (传送门)}\)

学过区间 DP 的，看到这题的第一反应都是：访问的地标一定是一个区间，并且在不断扩大，区间 DP！可看到数据范围，又瞬间放弃了。与 P1220 关路灯 不同，这题由于没有电量的消耗等额外因素，有这样一个小性质：

• 贝西的行走路线只可能是三种：一路向左，一路向右或者在中途折返一次。

一路向左和一路向右倒还好理解，可为什么最多只会折返一次呢？考虑以下情况：

如图，贝西从起点出发，折返了多次以访问所有地标。可问题是，以下做法不仅能满足要求，也更优：

换句话说，由于我们访问的地标总是一个区间，而从某个点开始走完整个区间分为三种情况：

1. 起点在区间左边，一路向右；
2. 起点在区间右边，一路向左；
3. 起点在区间里，先前往比较近的端点（左端点或者右端点），再前往另一个端点走完整个区间。

那么，现在问题来了：我们到底能走多少个地标呢？这取决于我们拥有的时间 \(t\)。换句话说，这是在满足条件（所用时间 \(\bm{\le t}\)）的情况下找最值。这不就是一个二分答案吗？而且单调性也是显然的：如果不能访问 \(x\) 个地标，那也访问不了 \(y(y>x)\) 个地标；如果能访问 \(x\) 个地标，那也访问的了 \(y(y<x)\) 个地标。

考虑二分答案。难点在于，如何设计 \(\text{check}\) 函数？假设当前二分答案猜测可以访问 \(X\) 个地标，则需要选择连续的 \(X\) 个地标（地标已经按坐标大小排序），即 \(x_1,x_2,\dots,x_X\) 或者 \(x_2,x_3,\dots,x_{X+1}\) 或者 \(x_3,x_4,\dots,x_{X+2}\ \dots\) 我们可以枚举这些区间的终点 \(i\in[X,n]\)，则区间的起点为 \(st=i-X+1\)。考虑上面的三种情况：一路向右，一路向左，起点在区间里，只要有一个满足条件就返回 \(\text{True}\)。条件判断的表达式分别为：

x[st] >= 0 && x[i] <= t

x[i] <= 0 && abs(x[st]) <= t

x[st] <= 0 && x[i] >= 0 && min(abs(x[st]), x[i]) + x[i] - x[st] <= t

完全再现了上面的三种情况。

如此一来，代码也就非常好写了：

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 5e4 + 5;

int t, n, a[N];

bool check(int X) {
	for (int i = X; i <= n; i++) {
		int st = i - X + 1;
		if (a[st] >= 0 && a[i] <= t)
			return 1;
		else if (a[i] <= 0 && abs(a[st]) <= t)
			return 1;
		else if (a[st] <= 0 && a[i] >= 0 && min(abs(a[st]), a[i]) + a[i] - a[st] <= t)
			return 1;
	}
	return 0;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> t >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + 1 + n);
	int l = -1, r = 5e4 + 1;
	while (l + 1 < r) {
		int mid = l + r >> 1;
		if (check(mid))
			l = mid;
		else
			r = mid;
	}
	cout << l;
	return 0;
}