codeforces1631D Range and Partition（二分/思维）

题目链接：codeforces 1631D

题目思路：

$y-x$ 越大，所选的区间长度越长，对应的分割后的个数越少，所以二分查找这个最小的差值。

那么怎么保证划分后的每个区间的在 $[x,y]$ 内的个数大于在 $[x,y]$ 外的个数？不妨反过来想，如果都保证了，那么所有的在 $[x,y]$ 内的个数一定大于在 $[x,y]$ 范围外的个数。所以我们可以在写 check 函数的时候，只要考虑这个区间的最大个数与此时区间外的个数之差是否大于等于 $k$ 即可。最后用贪心的方法去划分数组即可。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn], b[maxn];
int n, k;
bool check(int x) {
   
    int num = 0;
    for (int i = 1; i + x <= n; i++) {
   
        num = max(num, b[i+x] - b[i-1]);
    }
    return num - (n - num) >= k;
}
void solver() {
   
    memset(b, 0, sizeof(b));
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i], ++b[a[i]];
    for (int i = 1; i <= n; i++) b[i] += b[i-1];
    int l = 0, r = n-1; // 二分查找最小的 y - x
    while (l < r) {
   
        int mid = (l+r) >> 1;
        if (check(mid)) {
   
            r = mid;
        } else {
   
            l = mid + 1;
        }
    }
    int x, num = 0;
    for (int i = 1; i <= n-l; i++) {
   
        if (b[i+l] - b[i-1] >= num) num = b[i+l] - b[i-1], x = i;
    }
    cout << x << ' ' << x + l << endl;
    num = 0;
    int now = 0, last = 1;
    for (int i = 1; i < k; i++) {
   
        while (num <= 0) {
   
            now++;
            if (a[now] >= x && a[now] <= x + l) num++;
            else num--;
        }
        cout << last << ' ' << now << endl;
        num = 0, last = now + 1;
    }
    cout << last << ' ' << n << endl;
}
int main() {
   
    int _ = 1;
    cin >> _;
    while (_--) {
   
        solver();
    }
    return 0;
}