2093E – Min Max MEX
题目：https://codeforces.com/contest/2093/problem/E
E. Min Max MEX
time limit per test ：2 seconds
memory limit per test ：256 megabytes
You are given an array a of length n and a number k.
A subarray is defined as a sequence of one or more consecutive elements of the array. You need to split the array a into k non-overlapping subarrays b1,b2,…,bk
such that the union of these subarrays equals the entire array. Additionally, you need to maximize the value of x
, which is equal to the minimum MEX(bi)
, for i∈[1..k] MEX(v) denotes the smallest non-negative integer that is not present in the array v
.
Input
The first line contains an integer t
(1≤t≤104) — the number of test cases.
The first line of each test case contains two integers n， k (1 ≤ k ≤ n ≤ 2⋅105)
— the length of the array and the number of segments to > split the array into. The second line of each test case contains n integers ai (0≤ai≤109)
— the elements of the array.
It is guaranteed that the sum of n
across all test cases does not exceed 2e5
Output
For each query, output a single number — the maximum value x such that there exists a partition of the array a
into k subarrays where the minimum MEX equals x .
让我们说中文：
给你一个长度为 n 的数组 a 和一个整数 k。
我们定义 子数组 为数组中一段连续的元素序列。
你需要将整个数组 a 分成 k 个互不重叠的子数组 b₁, b₂, …, bₖ，使得这些子数组的并集恰好等于整个数组 a。
此外，你需要最大化一个值 x，这个值是所有子数组中 MEX(bᵢ) 的最小值
即：x = min(MEX(b₁), MEX(b₂), ..., MEX(bₖ))
MEX 的定义：
MEX(v) 表示在数组 v 中 没有出现的最小非负整数。
举例：
MEX([0, 1, 2]) = 3
MEX([1, 3, 4]) = 0
MEX([0, 2, 4]) = 1
输入格式：
****第一行包含一个整数 t（1 ≤ t ≤ 10⁴）—— 表示测试用例的数量。
接下来的每个测试用例包括两行：
****第一行包含两个整数 n 和 k（1 ≤ k ≤ n ≤ 2×10⁵）—— 数组长度和你需要分成的子数组数。
****第二行包含 n 个整数 aᵢ（0 ≤ aᵢ ≤ 10⁹）—— 数组的元素。
保证所有测试用例中 n 的总和不超过 2×10⁵。
输出格式：
****对于每个测试用例，输出一个整数 x，表示你能取得的最大值，使得存在一个将数组分成 k 段的方式，满足每一段的 MEX 至少为 x
Example:
Input
71 105 10 1 3 2 46 22 1 0 0 1 25 50 0 0 0 05 22 3 4 5 66 20 0 1 1 2 24 41 0 0 07 1 1 0 5 1 0 1 3 2 4 6 2 2 1 0 0 1 2 5 5 0 0 0 0 0 5 2 2 3 4 5 6 6 2 0 0 1 1 2 2 4 4 1 0 0 07 1 1 0 5 1 0 1 3 2 4 6 2 2 1 0 0 1 2 5 5 0 0 0 0 0 5 2 2 3 4 5 6 6 2 0 0 1 1 2 2 4 4 1 0 0 0
OutputCopy
15310101 5 3 1 0 1 01 5 3 1 0 1 0
官方题解：
****To solve the problem, we use binary search on the answer.
****要解决这个问题，我们可以对答案进行二分查找。
****To do this, we need to learn how to check for a given x
whether there exists a partition that allows achieving an answer of at least x. To do this, we will collect the segments one by one, that is, first we will find the minimal valid first segment, then the second, and so on.
****为此，我们需要知道如何判断给定一个值 x 时，是否存在一种划分方式，使得最终的答案至少为 x。为了解决这个问题，我们会一个一个地收集（划分）区间，也就是说，首先我们找到满足条件的最短第一个区间，然后是第二个，以此类推。
****Since the segments must be non-overlapping and must give the entire array in union, it means that in a correct partition there must exist a segment containing the first element; also, the MEX of this segment must be at least x
, which means it needs to be increased until the MEX becomes greater than or equal to x. As soon as this happens, it makes no sense to further increase the segment, so we move on to the next element and begin to select the next segment.
****由于这些区间必须互不重叠，并且它们的并集需要覆盖整个数组，因此在一个正确的划分中，必须存在一个区间包含第一个元素；此外，这个区间的 MEX 值必须至少为 x，也就是说我们需要扩展这个区间，直到它的 MEX 值大于等于 x。一旦达到了这个条件，就没有必要继续扩大当前区间了，我们可以从下一个元素开始选取下一个区间。
****To maintain MEX on a segment, we can use a counting array and a variable in which we store the current MEX. When a new number is added to the segment, we run a while loop, and while there is a number in the segment equal to the current MEX, we increase MEX by one. This works amortized in the number of elements in the segment, since MEX on the segment cannot be greater than the length of the segment.
****为了在一个区间上维护 MEX，我们可以使用一个计数数组和一个变量来存储当前的 MEX。当一个新数字加入到区间中时，我们可以运行一个 while 循环：只要当前的 MEX 在区间中已经出现，我们就将 MEX 加一。这种方法的摊还复杂度为该段区间元素的数量，因为一个区间的 MEX 值不会超过其长度。
Asymptotic of the solution: O(n⋅log(n))
算法的时间复杂度为：O(n⋅log(n))
可能还是点看不懂，那么我再说人话吧：
首先，这个思路把问题分解了：
-
我们用二分法枚举一个MEX，然后我们就查现在我们手上的数组能不能分成k个MEX的子数组
-
那么我们现在需要实现的就是检查当前数组是否能分成k份MEX等于所需MEX的子数组
-
那该如何实现呢？我们用贪心思想：开一个hash数组，存放某个数在“子数组”中出现的个数。然后我们从总数组的头开始检查，查一个数就放一个数到子数组里。
-
如果子数组的MEX达到所需MEX，那么子数组cnt++，并清空hash数组。
-
按照4,5，把数组全查完之后，我能知道整个数组能分为cnt个满足MEX条件的子数组，然后用cnt和k进行比较，从而判断check是true还是false
以下是代码实现：
#include <bits/stdc++.h>using namespace std;vector<int> nums(2e5 + 5, 0);//传参：数组、分割的块数、设定的检查的MEXbool check(vector<int>& v, int k, int m){int cnt = 0; //能达到MEX的块数int cur_mex = 0; //当前MEXfor (int i = 0; i < v.size(); i++) {//对于MEX而言，大于size的值对MEX的贡献为0，所以才有了这个if//如果发现可能有贡献，那么保存下来：这个数是存在的！if (v[i] <= v.size() + 1) {nums[v[i]] = 1;}//这是一个计算MEX的妙法：//如果保存的数直到MEX了，那就增加当前MEX//怎么理解呢，可以看一个例子/*如果我输入 4 2 0 1 3输入4：cur_mex = 0 nums[0]=0 因此不变输入2：cur_mex = 0 nums[0]=0 因此不变输入0：cur_mex = 0 nums[0]=1 因此mex++；再次进入循环：cur_mex = 1 nums[1]=0 因此不变输入1：cur_mex = 1 nums[1]=1 因此改变再次进入循环cur_mex = 2 nums[2]=1 因此mex++;（因为之前输入过2）输入3：cur_mex = 3 nums[3]=1 因此mex++;再次进入循环cur_mex = 4 nums[4]=1 因此mex++;所以我能轻松计算出此时的mex:也就是5了*/while (nums[cur_mex]) {cur_mex++;}//如果当前mex超出需要的m了，那么就可以将前面的定为一块//后面的便继续重新分块了if (cur_mex >= m) {cnt++; //分块数+1for (int j = 0; j < min(m + 1, (int)v.size() + 2); j++) {nums[j] = 0; //vector清零}cur_mex = 0; //当前mex清零}}//函数接近尾声，因此对nums清零处理for (int j = 0; j < v.size() + 2; j++) {nums[j] = 0;}//如果能分的块数大于需要分的块数，那么就可以返回yesreturn cnt >= k;}void solve(){int n, k;cin >> n >> k;vector<int> v(n);for (int i = 0; i < n; i++) {cin >> v[i];}int l = 0;int r = 1e9;//这里在二分检查MEX：因为只要小MEX能过，那么大MEX肯定也能过while (r - l > 1) {int m = (r + l) / 2;if (check(v, k, m)) {l = m;} else {r = m;}}cout << l << '\n';}signed main(){int t;cin >> t;for (int i = 0; i < t; i++) {solve();}return 0;}#include <bits/stdc++.h> using namespace std; vector<int> nums(2e5 + 5, 0); //传参：数组、分割的块数、设定的检查的MEX bool check(vector<int>& v, int k, int m) { int cnt = 0; //能达到MEX的块数 int cur_mex = 0; //当前MEX for (int i = 0; i < v.size(); i++) { //对于MEX而言，大于size的值对MEX的贡献为0，所以才有了这个if //如果发现可能有贡献，那么保存下来：这个数是存在的！ if (v[i] <= v.size() + 1) { nums[v[i]] = 1; } //这是一个计算MEX的妙法： //如果保存的数直到MEX了，那就增加当前MEX //怎么理解呢，可以看一个例子 /* 如果我输入 4 2 0 1 3 输入4：cur_mex = 0 nums[0]=0 因此不变 输入2：cur_mex = 0 nums[0]=0 因此不变 输入0：cur_mex = 0 nums[0]=1 因此mex++； 再次进入循环： cur_mex = 1 nums[1]=0 因此不变 输入1：cur_mex = 1 nums[1]=1 因此改变 再次进入循环 cur_mex = 2 nums[2]=1 因此mex++;（因为之前输入过2） 输入3：cur_mex = 3 nums[3]=1 因此mex++; 再次进入循环 cur_mex = 4 nums[4]=1 因此mex++; 所以我能轻松计算出此时的mex:也就是5了 */ while (nums[cur_mex]) { cur_mex++; } //如果当前mex超出需要的m了，那么就可以将前面的定为一块 //后面的便继续重新分块了 if (cur_mex >= m) { cnt++; //分块数+1 for (int j = 0; j < min(m + 1, (int)v.size() + 2); j++) { nums[j] = 0; //vector清零 } cur_mex = 0; //当前mex清零 } } //函数接近尾声，因此对nums清零处理 for (int j = 0; j < v.size() + 2; j++) { nums[j] = 0; } //如果能分的块数大于需要分的块数，那么就可以返回yes return cnt >= k; } void solve() { int n, k; cin >> n >> k; vector<int> v(n); for (int i = 0; i < n; i++) { cin >> v[i]; } int l = 0; int r = 1e9; //这里在二分检查MEX：因为只要小MEX能过，那么大MEX肯定也能过 while (r - l > 1) { int m = (r + l) / 2; if (check(v, k, m)) { l = m; } else { r = m; } } cout << l << '\n'; } signed main() { int t; cin >> t; for (int i = 0; i < t; i++) { solve(); } return 0; }#include <bits/stdc++.h> using namespace std; vector<int> nums(2e5 + 5, 0); //传参：数组、分割的块数、设定的检查的MEX bool check(vector<int>& v, int k, int m) { int cnt = 0; //能达到MEX的块数 int cur_mex = 0; //当前MEX for (int i = 0; i < v.size(); i++) { //对于MEX而言，大于size的值对MEX的贡献为0，所以才有了这个if //如果发现可能有贡献，那么保存下来：这个数是存在的！ if (v[i] <= v.size() + 1) { nums[v[i]] = 1; } //这是一个计算MEX的妙法： //如果保存的数直到MEX了，那就增加当前MEX //怎么理解呢，可以看一个例子 /* 如果我输入 4 2 0 1 3 输入4：cur_mex = 0 nums[0]=0 因此不变 输入2：cur_mex = 0 nums[0]=0 因此不变 输入0：cur_mex = 0 nums[0]=1 因此mex++； 再次进入循环： cur_mex = 1 nums[1]=0 因此不变 输入1：cur_mex = 1 nums[1]=1 因此改变 再次进入循环 cur_mex = 2 nums[2]=1 因此mex++;（因为之前输入过2） 输入3：cur_mex = 3 nums[3]=1 因此mex++; 再次进入循环 cur_mex = 4 nums[4]=1 因此mex++; 所以我能轻松计算出此时的mex:也就是5了 */ while (nums[cur_mex]) { cur_mex++; } //如果当前mex超出需要的m了，那么就可以将前面的定为一块 //后面的便继续重新分块了 if (cur_mex >= m) { cnt++; //分块数+1 for (int j = 0; j < min(m + 1, (int)v.size() + 2); j++) { nums[j] = 0; //vector清零 } cur_mex = 0; //当前mex清零 } } //函数接近尾声，因此对nums清零处理 for (int j = 0; j < v.size() + 2; j++) { nums[j] = 0; } //如果能分的块数大于需要分的块数，那么就可以返回yes return cnt >= k; } void solve() { int n, k; cin >> n >> k; vector<int> v(n); for (int i = 0; i < n; i++) { cin >> v[i]; } int l = 0; int r = 1e9; //这里在二分检查MEX：因为只要小MEX能过，那么大MEX肯定也能过 while (r - l > 1) { int m = (r + l) / 2; if (check(v, k, m)) { l = m; } else { r = m; } } cout << l << '\n'; } signed main() { int t; cin >> t; for (int i = 0; i < t; i++) { solve(); } return 0; }
暂无评论内容