题面

题目链接

题目大意

给定一个长度为$n$数组$a$和一个数字$k$，请你找出一个$[x,y]$，使其可以划分成$k$个区间，其中每个区间需满足如下要求：

• 每个区间中在$[x,y]$内的数严格多于在$[x,y]$之外的数。

请你找出符合要求并且使$y-x$最小的$[x,y]$。

题解

（其实感觉更像是官方题解的中文翻译）

像这样的区间划分问题，首先将其等效成一个$1,-1$数组。

假设我们已经设定了$[x,y]$，那么就得到一个数组$b$，其中$b_i$代表如果$a_i$在$[x,y]$内则为$1$，否则为$-1$，然后再计算数组$b$的前缀和$sum$。那么每一个符合要求的区间，就等价于这个区间的总和是正数（$1$的数量多于$-1$），要满足能够划分$k$个区间这样的要求，即是数组$b$的总和大于等于$k$（这$k$个区间和至少为$1$）。这转换成数学公式可以得到整个数组需要满足的最低要求，即整个数组中满足要求的$[x,y]的性质$：
$$ s_n \geqslant k \\\\ \sum_{i=1}^{n}b_i \geqslant k\\\\ \sum_{i=1}^{n}-1 + 2\cdot[x \leqslant a_i \leqslant y] \geqslant k\\\\ \Rightarrow \sum_{i=1}^n[x \leqslant a_i \leqslant y] \geqslant \lfloor\frac{n + k + 1}{2}\rfloor $$

所以，如果要找符合要求的$[x,y]$，我们可以在排序后的数组$a$（先复制数组$a$再排序），找一个区间$[i,j=i+\lfloor\frac{n + k + 1}{2}\rfloor]$（因为整个数组中最少要有这么多数在区间内，上面已经推过了），那么$[x,y]$就是$[b_i,b_j]$,在这基础上找到差值最小的即可。

划分区间的时候双指针贪心即可，就是每划分到一个区间和为$1$的时候就划分出来，划分$k-1$个，最后一个划分到$n$，就是可行解了。

Code(C++)

#include <iostream>
#include <array>
#include <algorithm>
#include <vector>

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mxe(x) (*max_element(all(x)))
#define mne(x) (*min_element(all(x)))
#define multicase() int sokuritszz, kase; for (std::cin >> sokuritszz, kase = 0; kase ++ , sokuritszz --;)

using i6  = long long;
using pii = std::array<int, 2>;
using str = std::string;

template<typename T>void ckmax(T &x, const T &a){ x > a ? x : x = a; }
template<typename T>void ckmin(T &x, const T &a){ x < a ? x : x = a; }

/*------------------------------------------------------------------*\
    Problem:  D. Range and Partition
    Contest:  Codeforces - Codeforces Round #768 (Div. 2)
        URL:  https://codeforces.com/contest/1631/problem/D
       Time:  2022.02.13 - 10:16:07
MemoryLimit:  256 MB
  TimeLimit:  2000 ms
     Author:  SokuRitszZ-Andrew1729
\*------------------------------------------------------------------*/

signed main() {
  std::cin.tie(0)->sync_with_stdio(false);
  multicase() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
      std::cin >> a[i];
    }
    auto b = a;
    std::sort(all(b));
    int in = n + k + 1 >> 1;
    int x = -1, y = n + 1;
    for (int i = 0; i <= n - in; ++i) {
      int L = b[i];
      int R = b[i + in - 1];
      if (R - L < y - x) {
        x = L;
        y = R;
      }
    }
    std::cout << x << ' ' << y << '\n';
    int last = -1;
    int mx = 0;
    int cur = 0;
    for (int i = 0; i < n; ++i) {
      cur += (x <= a[i] && a[i] <= y ? 1 : -1);
      if (cur > mx) {
        mx = cur;
        if (cur && cur <= k - 1) {
          std::cout << last + 2 << ' ' << i + 1 << '\n';
          last = i;
        }
      }
    }
    std::cout << last + 2 << ' ' << n << '\n';
  }
  return 0;
}