Codeforces Round#768(Div.2) D. Range and Partition

Codeforces Round#768(Div.2) D. Range and Partition 题意

给定一个数组，将这个数组分为k块，每一块要求在区间[x,y]内的数都要多于在区间外的数。求一个[x,y]使得y-x值最小，并输出k个区间的左右端点。

题解

我们先分析一下题意，找到我们需要解决的问题，以及问题中相互牵制的条件。
寻找到一个范围[x,y]，当范围大时显然我们可以任意分割数组，只要满足有k个区间即可。但是题目要求区间范围最小，范围小的话我们就不一定能满足分割出k个区间来
提示1：
专注于如何解决固定区间 [x,y] 的问题。
提示2：
将区间内的数字视为 +1，将其他数字视为 -1
提示3：
尝试将分区关联到具有递增序列的前缀和数组的有效子数组。
首先假设我们已经拥有了一个区间范围[x,y]，我们另设一个数组b，当x<=a[i]<=y,即a[i]在范围内时，b[i]=1反之b[i]等于-1.这样一个满足条件的区间，区间和大于0。
问题转换为，找到k个区间和大于等于1的区间。
接下来我们尝试解决这个问题，从全局考虑，要满足有k个子区间大于等于1，那总区间和一定需要大于k。

让我们对这个式子进行变形，先让每个b[i]都为-1，然后满足条件的a[i],b[i]值变为2，将式子化为

将式子常数展开，左边的-1求和可以放到右边然后整除。

这样这个式子的含义就变成了，整个数组中在范围[x,y]中的数的个数大于[k+n/2]上取整这么多即可。也就是说只要我们将分成k个区间这个条件简化为了最后这个式子。接下来我们只需要让范围差最小。
解决范围最小问题
既然是整个数组的问题，我们可以将原数组进行升序排列设为A，只需要满足下列式子：

循环遍历长度为（k+n+1）/2的区间保证满足可以分为k个区间的条件
分为k个区间
双指针输出，只要满足子区间和大于等于1就是一个答案。找到k-1个区间后输出最后一个区间

#include
#include
using namespace std;
const int MAXN = 2e5 + 5;
int t, n, k;
int a[MAXN], b[MAXN];
int main() {
	cin >> t;
	while (t--) {
		cin >> n >> k;
		int len = (n + k + 1) / 2;//确定最小长度
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			b[i] = a[i];
		}
		sort(b + 1, b + n + 1);//排序
		int x = 0, y = 1e9;
		for (int i = len; i <= n; i++)
			if (b[i] - b[i - len + 1] < y - x)//min(y-x)
				x = b[i - len + 1], y = b[i];
		cout << x << " " << y << endl;
		int s = 0, l = 1;
		for (int i = 1; i <= n; i++) {
			if (a[i] >= x && a[i] <= y) s++;
			else s--;
			if (s >= 1 && k > 1) {
				cout << l << " " << i << endl;
				l = i + 1;
				s = 0;
				k--;
			}
		}
		cout << l << " " << n << endl;
	}
	return 0;
}