CF1630B Range and Partition 题解

Range and Partition

传送门

题面翻译

给定一个由 $n$ 个整数组成的数组 $a$ ，找出数值范围 $[x,y]$ ( $x\le y$ )，并将 $a$ 分割成精确的 $k$ ( $1\le k\le n$ ) 子数组。( $1\le k\le n$ ) 子数组，以便：

• 每个子数组都由 $a$ 的几个连续元素组成，也就是说，对于某些 $l$ 和 $r$ ( $1\le l\le r\le n$ ) 来说，它等于 $a_l,a_{l+1},\dots ,a_r$ 。
• 来自 $a$ 的每个元素恰好属于一个子数组。
• 在每个子数组中， $[x,y]$ 范围内（包括 $[x,y]$ ）的元素个数是严格的。(包含在内）的元素个数严格大于范围之外的元素个数。当且仅当 $x\le a_i\le y$ 时，索引为 $i$ 的元素位于范围 $[x,y]$ 内。

打印任何能使 $y?x$ 最小化的解。

输入格式

输入由多个测试用例组成。第一行包含一个整数 $t$ ( $1\le t\le 3?10^4$ ) - 测试用例的数量。测试用例说明如下。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ （ $1\le k\le n\le 2?10^5$ ）–数组的长度 $a$ 和分区所需的子数组数。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le n$ )( $1\le a_i\le n$ ) 其中 $a_i$ 是数组的 $i$ /th 元素。

保证所有测试用例的 $n$ 之和不超过 $2?10^5$ 。

输出格式

每个测试用例打印 $k+1$ 行。

在第一行，打印 $x$ 和 $y$ - 已发现范围的极限。

然后打印 $k$ 行， $i$ /-th 应该包含 $l_i$ 和 $r_i$ （ $1\le l_i\le r_i\le n$ ）-- $i$ /th 子数组的极限。

您可以按照任意顺序打印子数组。

提示

在第一次测试中，应该只有一个子数组，它必须等于整个数组。在范围 $[1,2]$ 内有 $2$ 个元素，在 $[1,2]$ 外有 $0$ 个元素，如果选择的范围是 $[1,1]$ ，则在 $a_1$ 内有 $1$ 个元素，在 $a_2$ 外有 $1$ 个元素，答案无效。

在第二个测试中，可以选择范围 $[2,2]$ ，并将数组分成子数组 $(1,3)$ 和 $(4,4)$ ，在子数组 $(1,3)$ 中，范围内有 $2$ 个元素（ $a_2$ 和 $a_3$ ），范围外有 $1$ 个元素（ $a_1$ ），在子数组 $(4,4)$ 中只有 $1$ 个元素（ $a_4$ ），且在范围内。

在第三次测试中，可以选择范围 $[5,5]$ ，并将数组分成子数组 $(1,4)$ 、 $(5,7)$ 和 $(8,11)$ ，在子数组 $(1,4)$ 中，范围内有 $3$ 个元素，范围外有 $1$ 个元素；在子数组 $(5,7)$ 中，范围内有 $2$ 个元素，范围外有 $1$ 个元素；在子数组 $(8,11)$ 中，范围内有 $3$ 个元素，范围外有 $1$ 个元素。

题目描述

Given an array $a$ of $n$ integers, find a range of values $[x,y]$ ($x\le y$), and split $a$ into exactly $k$ ($1\le k\le n$) subarrays in such a way that:

• Each subarray is formed by several continuous elements of $a$, that is, it is equal to $a_l,a_{l+1},\dots ,a_r$ for some $l$ and $r$ ($1\le l\le r\le n$).
• Each element from $a$ belongs to exactly one subarray.
• In each subarray the number of elements inside the range $[x,y]$ (inclusive) is strictly greater than the number of elements outside the range. An element with index $i$ is inside the range $[x,y]$ if and only if $x\le a_i\le y$.

Print any solution that minimizes $y?x$.

Print any solution that minimizes $ y - x $ .

输入格式

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 3?10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1\le k\le n\le 2?10^5$) — the length of the array $a$ and the number of subarrays required in the partition.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le n$) where $a_i$ is the $i$-th element of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2?10^5$.

输出格式

For each test case, print $k+1$ lines.

In the first line, print $x$ and $y$ — the limits of the found range.

Then print $k$ lines, the $i$-th should contain $l_i$ and $r_i$ ($1\le l_i\le r_i\le n$) — the limits of the $i$-th subarray.

You can print the subarrays in any order.

样例 #1

样例输入 #1

3
2 1
1 2
4 2
1 2 2 2
11 3
5 5 5 1 5 5 1 5 5 5 1

样例输出 #1

1 2
1 2
2 2
1 3
4 4
5 5
1 1
2 2
3 11

提示

In the first test, there should be only one subarray, which must be equal to the whole array. There are $2$ elements inside the range $[1,2]$ and $0$ elements outside, if the chosen range is $[1,1]$, there will be $1$ element inside ($a_1$) and $1$ element outside ($a_2$), and the answer will be invalid.

In the second test, it is possible to choose the range $[2,2]$, and split the array in subarrays $(1,3)$ and $(4,4)$, in subarray $(1,3)$ there are $2$ elements inside the range ($a_2$ and $a_3$) and $1$ element outside ($a_1$), in subarray $(4,4)$ there is only $1$ element ($a_4$), and it is inside the range.

In the third test, it is possible to choose the range $[5,5]$, and split the array in subarrays $(1,4)$, $(5,7)$ and $(8,11)$, in the subarray $(1,4)$ there are $3$ elements inside the range and $1$ element outside, in the subarray $(5,7)$ there are $2$ elements inside and $1$ element outside and in the subarray $(8,11)$ there are $3$ elements inside and $1$ element outside.

$以上来自CodeForces，翻译工具：DeepL$

解题思路

问题转化：

对于这道题，最根本的问题是最小化的 $y?x$，而具体的形式是如何划分整个序列。若同时考虑这两个问题，事情会变得非常复杂，难以下手。所以不妨先扔下具体的形式，去考察最根本的问题。

性质：

划分为 $k$ 段时，在 $[x,y]$ 内的数总体上至少要比在此区间以外的数多 $k$ 个。

证明：

因为对于每个段，在区间里的数严格大于不在区间里的数，所以至少大 $1$，共 $k$ 段，所以至少大 $k$。

具体实现：

于是我们就得到这样一种做法：先将整个序列从小到大排序，然后用一个大小为 $n??\frac{n?k}{2}?$ 的滑动窗口去检测，窗口两端的数就是 $[x,y]$，取 $y?x$ 的最小值即可确定 $[x,y]$。
可以发现，让每一段都多一个，可以使滑动窗口尽可能小，这样 $y?x$ 也会相应更小，同时这样的一组 $[x,y]$ 一定有可行的划分方案。最后构造方案时也是每一段多一个就划开即可，时间复杂度 $O(n)$。注意每次将 $Answer$ 初始化为极大值。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Maxn = 200000 + 5;
int n, k, a[Maxn];
int tmp_a[Maxn];
int ans, ansl, ansr;
inline void solve() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		tmp_a[i] = a[i];
	}
	sort(a + 1, a + 1 + n);
	int top = n - (n - k) / 2;
	ans = INT_MAX;
	for (int i = 1; i <= n && i + top - 1 <= n; i++) {
		if (a[i + top - 1] - a[i] < ans) {
			ans = a[i + top - 1] - a[i];
			ansl = a[i], ansr = a[i + top - 1];
		}
	}
	cout << ansl << " " << ansr << endl;
	int tot = 0, st = 1, cnt = 1;
	for (int i = 1; i <= n; i++) {
		if (ansl <= tmp_a[i] && tmp_a[i] <= ansr) {
			tot += 1;
		} else {
			tot -= 1;
		}
		if (tot == 1) {
			cout << st << " ";
			if (cnt == k) {
				cout << n << endl;
				break;
			} else {
				cout << i << endl;
				tot = 0;
				cnt += 1;
				st = i + 1;
			}
		}
	}
}
inline void work() {
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	work();
	return 0;
}