题目描述

给定一个整数 $M$，对于任意一个整数集合 $S$，定义“校验值”如下:

从集合 $S$ 中取出 $M$ 对数(即 $2 \times M$ 个数，不能重复使用集合中的数，如果 $S$ 中的整数不够 $M$ 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合 $S$ 的“校验值”。

现在给定一个长度为 $N$ 的数列 $A$ 以及一个整数 $T$。

我们要把 $A$ 分成若干段，使得每一段的“校验值”都不超过 $T$。

求最少需要分成几段。

输入格式

第一行输入整数 $K$，代表有 $K$ 组测试数据。

对于每组测试数据，第一行包含三个整数 $N,M,T$ 。

第二行包含 $N$ 个整数，表示数列 $A _ 1, A _ 2 \cdots A _ N$。

输出格式

对于每组测试数据，输出其答案，每个答案占一行。

数据范围

$1 \leq K \leq 12,$
$1 \leq N,M \leq 500000,$
$0 \leq T \leq 10 ^ {18},$
$0 \leq A _ i \leq 2 ^ {20}$

输入样例：

2
5 1 49
8 2 1 7 9
5 1 64
8 2 1 7 9

输出样例：

2
1

算法1

(贪心 $+$ 二分) $\mathcal O(n ^ 2 \log n)$

首先，根据校验值的定义，要快速求出校验值，首先想到的办法肯定是爆搜贪心。

结论：将 $S$ 排序，每次取到 $S$ 中的最大值和最小值，最后计算出来的结果即为 $S$ 的校验值

证明：
这里只证明四个数的情况，多个数字同理。
设这四个数分别为 $A, B, C, D$，且 $0 < A \leq B \leq C \leq D$
那么只要证明 $(D - A) ^ 2 + (C - B) ^ 2 \geq (C - A) ^ 2 + (D - B) ^ 2$ 即可
$\because A \leq B$ 且 $C \leq D$
$\therefore (B - A) D \geq (B - A) C$
$\therefore BD - AD \geq BC - AC$
$\therefore BD + AC \geq BC + AD$
$\therefore -2BC - 2AD \geq -2BD - 2AC$
$\therefore A ^ 2 + B ^ 2 + C ^ 2 + D ^ 2 - 2 BC - 2 AD \geq A ^ 2 + B ^ 2 + C ^ 2 + D ^ 2 - 2 BD - 2 AC$
$\therefore (D - A)^ 2 + (C - B) ^ 2 \geq (C - A) ^ 2 + (D - B) ^ 2$
同理可证 $(D - A) ^ 2 + (C - B) ^ 2 \geq (B - A) ^ 2 + (D - C) ^ 2$

那么可以求出每段区间的校验值之后，如何找到一种划分区间最少的划分方案呢？

因为我们要划分的区间最少，所以要每次划分的区间尽可能长。

那么我们就可以每次划分区间的时候，用二分求出当前能划分的最长的区间。

时间复杂度

感谢楼下的墨染空巨佬指出此处错误！

每次二分的 check 中，要排一遍序，时间复杂度为 $\mathcal O(len \log len)$，其中 $len$ 是当前划分的区间长度。

假设第 $i$ 次二分划分的区间长度为 $len _ i$，一共划分了 $k$ 次，那么有 $len _ 1 + len _ 2 + \cdots + len _ k = n$

所以 $len _ 1 \log len _ 1 + len _ 2 \log len _ 2 + \cdots + len _ k \log len _ k \leq n \log n$

所以每次 check 的时间复杂度就是 $\mathcal O(n \log n)$

那么再算上二分内要check $\log n$ 次，每次二分的复杂度就是 $\mathcal O(n \log ^ 2 n)$

最坏情况下要调用 $n$ 次二分，所以，整体上看总时间复杂度为 $\mathcal O(n ^ 2 \log ^ 2 n)$

但实际上，时间复杂度最坏为 $\mathcal O(n ^ 2 \log n)$，证明如下。

考虑最坏情况，$T$ 极小，每次 $L$ 只 $+2$，导致二分 $n$ 次

考虑此情况下的每次二分

get 函数返回值一直大于 $T$，那么每次都会 r = mid，$mid$ 就会一直向 $l$ 跑

假设当前已经确定了前面 $L$ 个元素的分组，那么当前二分的区间即为 $[L, n)$，区间长度即为 $n - L$

那么二分中，第一次会调用 $get(L, L + {\large \frac {n - L} 2})$，第二次会调用 $get(L, L + {\large \frac {n - L} 4})$，以此类推

调用 $get(l, r)$ 的时间复杂度为 $(r - l) \log (r - l)$

那么二分中，第一次调用 $get$ 的时间复杂度为 ${\large \frac {n - L} 2} \log {\large \frac {n - L} 2}$，第二次为 ${\large \frac {n - L} 4 }\log {\large \frac {n - L} 4}$，以此类推

所以二分的总复杂度即为 ${\large \frac {n - L} 2} \log {\large \frac {n - L} 2} + {\large \frac {n - L} 4} \log {\large \frac {n - L} 4} + \cdots + 1 \log 1$

设 $l = 2 ^ {\lceil \log _ 2 (n - L) \rceil}$（即比 $n - L$ 大的最小的 $2$ 的整次幂）

则上述复杂度就低于 ${\large \frac l 2} \log {\large \frac l 2} + {\large \frac l 4} \log {\large \frac l 4} + \cdots + 1 \log 1$

以下证明由 @[张缘]{:target=”blank”} 给出：

因为 ${\large \frac l 2} \log {\large \frac l 2} + {\large \frac l 4} \log {\large \frac l 4} + \cdots + 1 \log 1 \leq (\frac l 2 + \frac l 4 + \cdots + 1) \log \frac l 2 = (l - 1) \log \frac l 2 \leq l \log l$

于是每次二分复杂度为 $O(n \log n)$。总复杂度为 $O(n ^ 2 \log n)$。

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 500005;

int n, m;
int ans;              // 存答案
ll T;                 // 题目中的 T
ll w[N], t[N];        // w 是输入的数组，t 是用于求校验值的数组

ll sq(ll x)           // 返回 x 的平方
{
    return x * x;
}

ll get(int l, int r)  // 求原数组区间 [l, r] 的校验值
{
    int k = 0;        // 要先把 w 的 [l, r] 这段复制到 t 中，用 k 记录 t 的长度。
    for (int i = l; i <= r; i ++ ) // 从 l 到 r 枚举一遍，将 w 数组复制到 t 数组中
        t[k ++ ] = w[i];
    sort(t, t + k);   // 将复制过来的数排序
    ll sum = 0;       // 存返回的校验值
    for (int i = 0; i < m && i < k; i ++ , k -- )
        sum += sq(t[i] - t[k - 1]); // 双指针，i 指向当前集合中剩余的最小数，k 指向当前集合中剩余的最大数
    return sum;
}

int main()
{
    int K;            // 测试数据组数
    cin >> K;
    while (K -- )     // 不写奇怪的 for 循环了qwq
    {
        cin >> n >> m >> T;
        for (int i = 0; i < n; i ++ ) cin >> w[i];
        ans = 0;      // 答案归零
        int start = 0;    // start 记录当前剩余的区间左端点
        while (start < n) // start < n 说明当前数组还有值，需要继续划分。结束时 start 应等于 n 
        {
            int l = start, r = n, mid; // 二分求出当前能划分的最长的区间
            while (l < r) // 二分板子
            {
                mid = l + r >> 1;
                if (get(start, mid) > T) r = mid;
                else    l = mid + 1;
            }
            start = r;    // 二分完后，r 即当前可划分的最长区间的下一个位置，将 start 制为 r。
            ans ++ ;      // 每次划分完一个区间，ans ++ 
        }
        printf("%d\n", ans);
    }
    return 0;
}

算法2

(倍增) $O(n \log ^ 2 n)$

设当前划分区间起点为 $start$

1. 让 $len = 1, end = start$
2. 每次判断区间 $[start, end + len)$ 的校验值是否合法（注意：区间左闭右开）
3. 如果合法，那么让 $end + len$，然后 $len \times 2$，重复 2
4. 如果不合法，那么 $len \div 2$。
   • 如果 $len = 0$，那么跳出。
   • 否则重复 2

每次跳出后，由于区间 $[start, end)$ 是左闭右开的，直接让 $start = end$，$ans ++ $ 即可

时间复杂度

二分的最坏情况，反而对倍增而言是最好情况

所以倍增的时间复杂度不同于二分，为 $\mathcal O(n \log ^ 2 n)$，以下证明由 @[张缘]{:target=”blank”} 给出：

设答案中每段区间的长度分别为 $len _ 1, len _ 2, \cdots, len _ k$，对于每个 $len _ i$，需要倍增 $O(\log n)$ 次

这样每次找到一段，需要 $O(\log n len _ i \log len _ i)$ 的时间

总时间复杂度即为 $O((len _ 1 \log len _ 1 + len _ 2 \log len _ 2 + \cdots + len _ k) \log n) = O(n \log ^ 2 n)$

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 500005;

int n, m;
int ans;
ll T;
ll w[N], t[N];

ll sq(ll x)
{
    return x * x;
}

ll get(int l, int r)  // 计算原数组左闭右开区间 [l, r) 的校验值
{
    int k = 0;
    for (int i = l; i < r; i ++ )
        t[k ++ ] = w[i];
    sort(t, t + k);
    ll sum = 0;
    for (int i = 0; i < m && i < k; i ++ , k -- )
        sum += sq(t[i] - t[k - 1]);
    return sum;
}

int main()
{
    int K;
    scanf("%d", &K);
    while (K -- )
    {
        scanf("%d %d %lld\n", &n, &m, &T); // 不用 scanf 的话，这么做有一个点会 TLE
        for (int i = 0; i < n; i ++ )
            scanf("%lld", &w[i]);
        ans = 0;
        int start = 0, end = 0;            // start 记录剩余区间开头节点，end 记录当前考虑区间的尾结点（左闭右开）
        while (end < n)
        {
            int len = 1;                   // len 初始化为 1
            while (len)                    // len 为 0 自动跳出
            {
                if (end + len <= n && get(start, end + len) <= T) // 如果说 len + end 还在 n 以内，且区间 [start, end + len) 的校验值不大于 T
                    end += len, len <<= 1; // 那么 end += len，len *= 2
                else    len >>= 1;         // 否则 len /= 2
            }
            start = end;                   // 让 start 指向当前区间末尾结点的下一个位置，由于区间是左闭右开的，所以直接指向 end 就可以了
            ans ++ ;                       // 每次循环都找到了一个区间，所以让 ans ++ 
        }
        printf("%d\n", ans);
    }
    return 0;
}
// 偷个懒，少写点注释 ( ￣▽￣)σ

算法3

(倍增 $+$ 归并) $\mathcal O(n \log n)$

上述代码中，在处理 $[start, end)$ 的时候，已经将 $[start, end)$ 排好序了，所以不需要在处理 $[start, end + len)$ 时再排序。
处理 $[start, end + len)$ 时，只需要将 $[end, end + len)$ 排序，然后将 $[start, end)$ 与 $[end, end + len)$ 这两段区间进行归并即可。
详见代码注释。

时间复杂度

假设一共将数组划分成了 $k$ 个区间（这里的区间指的是每次二分里面check的区间总和，并非题目中所指的区间），每个区间的长度分别为 $len _ 1, len _ 2, \cdots, len _ k$。
那么按上述方法只需要将每个区间排序一遍，所以时间复杂度为 $\mathcal O(len _ 1 \log len _ 1 + len _ 2 \log len _ 2 + \cdots + len _ k \log len _ k) \leq \mathcal O(n \log n)$
加上每次归并的时间复杂度为 $O(n)$，总的时间复杂度为 $\mathcal O(n + n \log n) = \mathcal O(n \log n)$

C++代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 500005;

int n, m;
int ans;
ll T;
ll w[N], t[N];
ll tmp[N];

ll sq(ll x)
{
    return x * x;
}

bool check(int l, int mid, int r)           // 判断区间 [l, r) 是否合法，并将 t 中的 [l, mid) 区间和 [mid, r) 区间合并到 tmp 中
{
    for (int i = mid; i < r; i ++ )         // 将 w 数组的 [l, r) 区间复制到 t 的 [l, r) 区间中
        t[i] = w[i];
    sort(t + mid, t + r);                   // 将 t 的 [mid, r) 排序
    int i = l, j = mid, k = 0;              // 双指针进行区间合并
    while (i != mid && j != r)              // 当 i 不到 mid 且 j 不到 r 时，执行循环
        if (t[i] < t[j])                    // 如果 t[i] 比 t[j] 小，那么将 t[i] 放入 tmp 中
            tmp[k ++ ] = t[i ++ ]; 
        else                                // 否则将 t[j] 放入 tmp 中
            tmp[k ++ ] = t[j ++ ];
    while (i != mid) tmp[k ++ ] = t[i ++ ]; // 处理剩下的元素
    while (j != r) tmp[k ++ ] = t[j ++ ];
    ll sum = 0;                             // 计算校验值
    for (i = 0; i < m && i < k; i ++ , k -- )
        sum += sq(tmp[i] - tmp[k - 1]);
    return sum <= T;                        // 返回当前区间 [l, r) 是否合法
}

int main()
{
    int K;
    scanf("%d", &K);
    while (K -- )
    {
        scanf("%d %d %lld\n", &n, &m, &T);
        for (int i = 0; i < n; i ++ )
            scanf("%lld", &w[i]);
        ans = 0;
        int len;
        int start = 0, end = 0;
        while (end < n)
        {
            len = 1;
            while (len)
            {
                if (end + len <= n && check(start, end, end + len)) // 如果 w 的 [start, end + len) 区间合法
                {
                    end += len, len <<= 1;
                    if (end >= n) break ;               // 一个小剪枝，如果 end >= n，那么直接跳出
                    for (int i = start; i < end; i ++ ) // 在 check 时，已经将 t 数组的 [start, end + len) 这段区间归并在 tmp 中了。现在只需要将 tmp 中的有序数组复制到 t 中即可
                        t[i] = tmp[i - start];          // 复制的时候注意下标变换，tmp 是从 0 开始存的，t 是从 start 开始存的
                }
                else    len >>= 1;
            }
            start = end;
            ans ++ ;
        }
        printf("%d\n", ans);
    }
    return 0;
}

$$ $$

$$ $$

$$ $$

$$ $$

$$ $$

$$ $$

$$ $$