题目描述

有 $N$ 人站在一条数轴上。他们人手一个烟花，每人手中的烟花都恰好能燃烧 $T$ 秒。每个烟花只能被点燃一次。
$1$ 号站在原点，$i$ 号 $(1 \le i \le N)$ 到 $1$ 号的距离为 $X_i$。保证 $X_1 = 0$，$X_1, X_2, …, X_N$ 单调递增（可能有人位置重叠）
开始时，$K$ 号的烟花刚开始燃烧，其他人的烟花均未点燃。他们的点火工具坏了，只能用燃着的烟花将未点燃的烟花点燃。当两人位置重叠且其中一人手中的烟花燃着时，另一人手中的烟花就可以被点燃。忽略点火所需时间。
求至少需要以多快的速度跑，才能点燃所有人的烟花（此时可能有些人的烟花已经熄灭了）。速度必须是一个非负整数

数据范围

对 $100\%$ 的数据，$1 \le K, N \le 10^5, ~ 1 \le T \le 10^9, ~ 0 \le X_i \le 10^9, ~ X_1 = 0$

题解

很显然所有人一定会不断向拿烟花的人靠近

可以发现，一个拿烟花棒的人和另一个人相遇时，让另一个人跟着拿烟花的人走直至烟花在灭掉的瞬间将烟花传递的情况和在相遇时传递时一样的（注意相对位置，仔细想一下就可以证明）

也就是说，整个过程可以看作只有一个拿烟花的人，进一步推理可以发现，拿烟花的人和另一个人相遇等价于他的烟花燃烧时间加上 $T$（在最优情况下）

又两人相向而行时相对速度为 $2v$，那么对于一个区间 $[L, R]$，它满足条件的必要条件即是
$$
2vT(R - L) \ge x_R - x_L
$$
而我们从 $K$ 开始不断向两边扩展，使得每次扩展都满足条件，那么扩展到 $[L, R]$ 时，该条件便成为充要条件

对上式进行变换，有
$$
x_L - 2vTL \ge x_R - 2vTR
$$
不妨令 $a_i = x_i - 2vTi$，那么该条件便转化为 $a_L \ge a_R$

进行二分答案

在 $check$ 时进行贪心，贪心扩展当前所到区间 $[l, r]$，对 $l$，不断找到一个 $k$，使得 $a_k \ge a_l \cap k < l \cap a_k \ge a_r$，对 $r$ 同理，最终会扩展到一个极大区间 $[ll, lr]$

若 $ll = 1 \cap lr = N$，那么就可以返回 $true$，如若不然，则观察当前情况

现在局面是 $l, r$ 不能继续往左右扩展，也就是 $l$ 往左不存在 $a_k \ge a_l$ 或 $a_k \ge a_r$，$r$ 往右不存在 $a_k \le a_r$ 或 $a_k \le a_l$，对不存在 $a_{k_1} \ge a_r \cup a_{k_2} \le a_l$ 的局面，显然就直接返回 $false$，那么对另一种局面，考虑 $l$ 往左，说明一段一段的最大值是递减的，但是不妨将其反过来，那不就和上面 $K$ 往两边扩展的情况一样了吗，$r$ 往右同理，那么现在要做的就是重新令 $l = 1, r = N$，然后向内缩，看能否缩到 $[ll, lr]$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;

const int MAXN = 1e05 + 10;

const int INF = 1e09;

int N, K, T;
int X[MAXN];

LL a[MAXN];
bool check (int v) {
	for (int i = 1; i <= N; i ++) a[i] = X[i] - 2ll * v * T * i;
	if (a[1] < a[N]) return false;
	int l = K, r = K, ll = K, lr = K;
	for (int i = l; i >= 1; i --)
		if (a[i] >= a[ll])
			ll = i;
	for (int i = r; i <= N; i ++)
		if (a[i] <= a[lr])
			lr = i;
	while (l != ll || r != lr) {
		int pl, pr; bool suc = false;
		for (pl = l; pl > ll; ) {
			if (a[pl - 1] < a[r]) break;
			if (a[-- pl] >= a[l]) break;
		}
		if (pl < l && a[pl] >= a[l]) { l = pl; suc = true; }
		for (pr = r; pr < lr; ) {
			if (a[pr + 1] > a[l]) break;
			if (a[++ pr] <= a[r]) break;
		}
		if (pr > r && a[pr] <= a[r]) { r = pr; suc = true; }
		if (! suc) return false;
	}
	l = 1, r = N;
	while (l != ll || r != lr) {
		int pl, pr; bool suc = false;
		for (pl = l; pl < ll; ) {
			if (a[pl + 1] < a[r]) break;
			if (a[++ pl] >= a[l]) break;
		}
		if (pl > l && a[pl] >= a[l]) { l = pl; suc = true; }
		for (pr = r; pr > lr; ) {
			if (a[pr - 1] > a[l]) break;
			if (a[-- pr] <= a[r]) break;
		}
		if (pr < r && a[pr] <= a[r]) { r = pr; suc = true; }
		if (! suc) return false;
	}
	return true;
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum (), K = getnum (), T = getnum ();
	for (int i = 1; i <= N; i ++) X[i] = getnum ();
	int left = 0, right = INF, ans;
	while (left <= right) {
		int mid = (left + right) >> 1;
		if (check (mid)) { ans = mid; right = mid - 1; }
		else left = mid + 1;
	}
	printf ("%d\n", ans);

	return 0;
}