本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-05-14 11:01:37

题解思路：

假设我们有若干个长为 $n$ 的数组。

有 $len$ 个满足条件 $A$ 的数字。

我们至少要分成 $k$ 组。

每组都要满足 $A$ 的数的个数 $>$ 不满足 $A$ 的个数。

那么每组若只多一个，那么 $n$ 里面满足条件 $A$ 的至少要比不满足的多 $k$ 个，

所以一组里不满足的就有 $\left \lfloor \frac{(n-k)}{2} \right \rfloor$ 个。

所以满足的条件就是 $n - \left \lfloor \frac{(n-k)}{2} \right \rfloor$。

你选的数 $len = \left \lceil \frac{(n-k)}{2} \right \rceil = \left \lfloor \frac{(n-k + 1)}{2} \right \rfloor$

那么你的值域区间就是 $\left[ a_i,a_{i+len-1}\right]$。

排完序之后，遍历一下，你就能知道他的最小的值域区间是多少。

但是知道了最小的值域我们还要构造一个区间的分开方式

我们回到原序列，若有一个在所选区间的数，就让计数器 $+1$。

若不在值域的数，那么计数器 $-1$。

那么计数器 $>1$ 的区间，就把左右端点记下来，若最后的数字没有分完就直接把他移到右端点就可以了。

最后直接输出左右端点就可以了。

AC CODE:

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
const int N = 200010;
int n;
int cnt;
int tot , k;
int a[N] , b[N];
int l[N] , r[N];
int ansl , ansr;
vector <int> p[N];
void solve() {
	scanf ("%d%d" , &n , &k);
	tot = 0;
	int len = (n + k + 1) \/ 2;\/\/计算一个区间的长度
	for (int i = 1; i <= n; i++) {
		scanf ("%d" , &a[i]);
		b[i] = a[i];\/\/b保存的是排序后的数组
	}
	sort(b + 1, b + 1 + n);\/\/排序
	ansl = 1, ansr = len;
	for (int i = 2; i + len - 1 <= n; i++) 
		if (b[i + len - 1] - b[i] < b[ansr] - b[ansl]) 
			ansl = i, ansr = i + len - 1;
	for (int i = 1, u = 1; i <= k; u++, i++) {
		l[i] = u;
		for (int cnt = 0;; u++) {
			if (a[u] >= b[ansl] && a[u] <= b[ansr]) \/\/若满足条件
				cnt++;\/\/计数器++
			else \/\/否则
				cnt--;\/\/计数器--
			if (cnt > 0) {\/\/只要大于0，就是
				r[i] = u;
				break;
			}
		}
	}
	r[k] = n;
	printf ("%d %d\n" , b[ansl] , b[ansr]);
	for (int i = 1; i <= k; i++) \/\/输出
		printf ("%d %d\n" , l[i] , r[i]);
}
int main() {
	int T;
	scanf ("%d" , &T);
	while (T --)
		solve();
	return 0;
}

码字不易，求赞！