题意

给一组数据，从左到右开始，寻找最小的x，使得第1个元素到第x个元素中，至少存在m个数据，最小值与最大值之差不超过K。

INPUT

第一行是T，代表数据组数

每组数据的第一行是三个整数，n、m、k。n代表数据个数，m、n、k小于1e5。

第二行以此是n个数据，每个数据小于1e5。

OUPUT

如果存在这样的x，则输出x；否则输出"impossible"。

解析

二分法来处理原数据。如果中间元素满足题意，那么检测左区间；否则检测右区间。

代码

#include <stdio.h>

#include <string>

#include <stdlib.h>

#include <iostream>

#include <vector>

#include <string.h>

#include <algorithm>

using namespace std;

const int A = 1e5 + 10;

int a[A], b[A];

int n, m, k;

bool check(int x) {

	memcpy(b, a, sizeof(a));

	sort (b + 1, b + x + 1);

	for (int i = 1; i + m - 1 <= x; i++) {

		int s = i, e = i + m - 1;

		if (b[e] - b[s] <= k) return true;

	}

	return false;

}

int main() {

	int T;

	cin >> T;

	while (T--) {

		cin >> n >> m >> k;

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

			cin >> a[i];

		}

		int ans = -1;

		int l = m, r = n;

		while (l <= r) {

			int mid = (l + r) >> 1;

			if (check(mid)) {

				ans = mid;

				r = mid - 1;

			}

			else{

				l = mid + 1;

			}

		}

		if (ans == -1)

			cout << "impossible" << endl;

		else

			cout << ans << endl;

	}

	return 0;

}