【BZOJ 4582】【Usaco2016 Open】Diamond Collector

http://www.lydsy.com/JudgeOnline/problem.php?id=4582

排好序后用两个指针直接\(O(n)\)扫，貌似这个东西学名"two pointers"？

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 50003;

int pre[N], aft[N], a[N], n, k, cnt;

int main() {

	scanf("%d %d", &n, &k);

	for (int i = 1; i <= n; ++i)

		scanf("%d", a + i);

	stable_sort(a + 1, a + n + 1);

	int tail = 1, head = n;

	for (int i = 1; i <= n; ++i) {

		while (tail <= n && a[tail] - a[i] <= k) ++tail;

		aft[i] = tail - i;

	}

	for (int i = n; i >= 1; --i) {

		while (head >= 1 && a[i] - a[head] <= k) --head;

		pre[i] = i - head;

	}

	for (int i = 2; i <= n; ++i)

		pre[i] = max(pre[i], pre[i - 1]);

	for (int i = n - 1; i >= 1; --i)

		aft[i] = max(aft[i], aft[i + 1]);

	int ans = 0;

	for (int i = 2; i <= n; ++i)

		ans = max(ans, pre[i - 1] + aft[i]);

	printf("%d\n", ans);

	return 0;

}