\(\color{black}\text{P2390 地标访问 (传送门)}\)
学过区间 DP 的,看到这题的第一反应都是:访问的地标一定是一个区间,并且在不断扩大,区间 DP!可看到数据范围,又瞬间放弃了。与 P1220 关路灯 不同,这题由于没有电量的消耗等额外因素,有这样一个小性质:
- 贝西的行走路线只可能是三种:一路向左,一路向右或者在中途折返一次。
一路向左和一路向右倒还好理解,可为什么最多只会折返一次呢?考虑以下情况:
如图,贝西从起点出发,折返了多次以访问所有地标。可问题是,以下做法不仅能满足要求,也更优:
换句话说,由于我们访问的地标总是一个区间,而从某个点开始走完整个区间分为三种情况:
- 起点在区间左边,一路向右;
- 起点在区间右边,一路向左;
- 起点在区间里,先前往比较近的端点(左端点或者右端点),再前往另一个端点走完整个区间。
那么,现在问题来了:我们到底能走多少个地标呢?这取决于我们拥有的时间 \(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;
}
标签:二分,P2390,int,一路,st,访问,地标,区间
From: https://www.cnblogs.com/Weekoder/p/18240172