Codeforces 1168A（二分check）

关键是check。要注意到其实有了mid以后每个位置都是独立的，它能从哪走到哪是固定了的，只要从左到右尽量贪心压着最小值即可。

#include <cstdio>

const int maxn = 3e5 + 5;
int n, m, a[maxn];

bool ok(int mid) {
	for (int i = 1, pre = 0; i <= n; i++) {
		int l = a[i], r = a[i] + mid;
		if ((l <= pre && pre <= r) || (l <= pre + m && pre + m <= r))
			continue;
		if (pre < l)	pre = l;
		else	return 0;
	}
	return 1;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);

	int l = 0, r = m, ans;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (ok(mid))	ans = mid, r = mid - 1;
		else	l = mid + 1;
	}
	return !printf("%d
", ans);
}