Codeforces 1156C 尺取法 / 二分

题意：给你一个数组，问里面最多能匹配出多少对，满足abs(a[i] - a[j]) >= k;

思路：首先肯定要排序。

思路1（尺取法）：看了dreamoon的代码明白的。我们可以寻找一个最长的段，这段的最大值和最小值的差小于k，假设数组长度是n，那么答案是min(n / 2, n - mx)。为什么呢？如果mx大于n / 2，容易发现我们最多只能构造出n - mx对，mx小于同理。

代码：

#include <bits/stdc++.h>

#define LL long long

#define db double

#define INF 0x3f3f3f3f

#define pii pair<int, int>

using namespace std;

const int maxn = 200010;

int a[maxn], re[maxn], tot;

bool v[maxn];

int main() {

	int n, m, ans = 0;

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

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

		scanf("%d", &a[i]);

	}

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

	int l = 1, r = 1;

	int mx = 0;

	for(; r <= n; r++) {

		while(a[l] + m <= a[r]) l++;

		mx = max(mx, r - l + 1);

	}

	printf("%d\n", min(n / 2, n - mx));

}

思路2：二分。

二分取前几个元素，判断只和后几个元素能不能匹配即可。

巴特西

Codeforces 1156C 尺取法 / 二分

最新文章

热门文章