CF1630B题解

· · 题解

题解思路：

假设我们有若干个长为 n 的数组。

有 len 个满足条件 A 的数字。

我们至少要分成 k 组。

每组都要满足 A 的数的个数 > 不满足 A 的个数。

那么每组若只多一个，那么 n 里面满足条件 A 的至少要比不满足的多 k 个，

所以一组里不满足的就有 \left \lfloor \frac{(n-k)}{2} \right \rfloor 个。

所以满足的条件就是 n - \left \lfloor \frac{(n-k)}{2} \right \rfloor。

你选的数 len = \left \lceil \frac{(n-k)}{2} \right \rceil = \left \lfloor \frac{(n-k + 1)}{2} \right \rfloor

那么你的值域区间就是 \left[ a_i,a_{i+len-1}\right]。

排完序之后，遍历一下，你就能知道他的最小的值域区间是多少。

但是知道了最小的值域我们还要构造一个区间的分开方式

我们回到原序列，若有一个在所选区间的数，就让计数器 +1。

若不在值域的数，那么计数器 -1。

那么计数器 >1 的区间，就把左右端点记下来，若最后的数字没有分完就直接把他移到右端点就可以了。

最后直接输出左右端点就可以了。

AC CODE:

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
const int N = 200010;
int n;
int cnt;
int tot , k;
int a[N] , b[N];
int l[N] , r[N];
int ansl , ansr;
vector <int> p[N];
void solve() {
    scanf ("%d%d" , &n , &k);
    tot = 0;
    int len = (n + k + 1) / 2;//计算一个区间的长度
    for (int i = 1; i <= n; i++) {
        scanf ("%d" , &a[i]);
        b[i] = a[i];//b保存的是排序后的数组
    }
    sort(b + 1, b + 1 + n);//排序
    ansl = 1, ansr = len;
    for (int i = 2; i + len - 1 <= n; i++) 
        if (b[i + len - 1] - b[i] < b[ansr] - b[ansl]) 
            ansl = i, ansr = i + len - 1;
    for (int i = 1, u = 1; i <= k; u++, i++) {
        l[i] = u;
        for (int cnt = 0;; u++) {
            if (a[u] >= b[ansl] && a[u] <= b[ansr]) //若满足条件
                cnt++;//计数器++
            else //否则
                cnt--;//计数器--
            if (cnt > 0) {//只要大于0，就是
                r[i] = u;
                break;
            }
        }
    }
    r[k] = n;
    printf ("%d %d\n" , b[ansl] , b[ansr]);
    for (int i = 1; i <= k; i++) //输出
        printf ("%d %d\n" , l[i] , r[i]);
}
int main() {
    int T;
    scanf ("%d" , &T);
    while (T --)
        solve();
    return 0;
}

码字不易，求赞！