P10455题解

· · 题解

题意概述

给定正整数 n，m，k，与非负整数 P_1,P_2,\cdots,P_n，问最少要将序列 P_1,P_2,\cdots,P_n 划分成多少个连续的子段，使每一段的 SPD 值小于等于 k。
每段的 SPD 值的计算方式为：选 \min(\lfloor \frac{n}{2} \rfloor, m) 对数，每对的两个数的差的平方的和的最大值。
想看题目就点这里：P10455 Genius Acm。

SPD 值的求法

比如，给定正整数 n，m 与整数 a_1,a_2,\cdots,a_n，求 a 序列的 SPD 值。
最暴力的方法当然是枚举每种选择数对的方式并求出每种选择方式的结果，最后求一个最大值。当然，这样的时间复杂度太高，难以接受。所以我们想到，如何选择数对它的结果就会最大呢？
当然，结果用贪心很容易想到，就是第 1 小的数匹配第 1 大的数、第 2 小的数匹配第 2 大的数、\cdots、第 \min(\lfloor \frac{n}{2} \rfloor, m) 小的数匹配第 \min(\lfloor \frac{n}{2} \rfloor, m) 大的数。那么为什么呢？能否证明这一点呢？下面给出一个证明：

证明：
不妨 a_1 \le a_2 \le \cdots \le a_n，令 K = \min(\lfloor \frac{n}{2} \rfloor, m)，并假设所选的 K 对数分别为 (x_1, y_1),(x_2,y_2),\cdots,(x_K,y_K)。即要最大化 S = \sum_{i = 1}^K (x_i - y_i)^2。
固定所选的 2K 个元素，且不妨 x_i < y_i，则若存在正整数 s, t(1 \le s, t \le K)，使 x_s \le x_t 且 y_s < y_t。
令正整数 y'_1,y'_2,\cdots,y'_K 为交换 y_s 与 y_t 后的 y_1,y_2,\cdots,y_K，即（i 为正整数，且 i \le K）：

y'_i = \begin{cases} y_t & i = s \\ y_s & i = t \\ y_i & i \ne s \text{ 且 } i \ne t \end{cases}

则原来配对方案 (x_1,y_1),(x_2,y_2),\cdots,(x_K,y_K) 每对数的差的平方的和 S 减去交换 y_s 与 y_t 后的配对方案 (x_1,y'_1),(x_2,y'_2),\cdots,(x_K,y'_K) 的差的平方的和 S' 的结果如下：

\begin{aligned} S - S' &= \sum_{i=1}^K (x_i - y_i)^2 - \sum_{i=1}^K (x_i - y'_i)^2 \\ &= \sum_{i=1}^K ({x_i}^2 + {y_i}^2 - 2x_iy_i) - \sum_{i=1}^K ({x_i}^2 + {y'_i}^2 - 2x_iy'_i) \\ &= (\sum_{i=1}^K {x_i}^2 + \sum_{i=1}^K {y_i}^2 - 2\sum_{i=1}^K x_iy_i) - (\sum_{i=1}^K {x_i}^2 + \sum_{i=1}^K {y'_i}^2 - 2\sum_{i=1}^K x_iy'_i) \\ &= 2(\sum_{i=1}^K x_iy'_i - \sum_{i=1}^K x_iy_i) \\ &= 2((x_sy_t+x_ty_s) - (x_sy_s + x_ty_t)) \\ &= 2(x_s - x_t)(y_t - y_s) \\ &\le 0 \end{aligned} \therefore S' \ge S

即，若存在正整数 s, t(1 \le s, t \le K)，使 x_s \le x_t 且 y_s < y_t，则交换 y_s 与 y_t 后每对数的差的平方的和不会更小。
所以，给 x_1,x_2,\cdots,x_K 定序，令 x_1 \le x_2 \le \cdots \le x_K，则最优解一定满足 y_1 \ge y_2 \ge \cdots \ge y_K。即：满足 x_1 \le x_2 \le \cdots \le x_K \le y_K \le y_{K-1} \le \cdots \le y_1 的一定是一组最优解。也就是在固定的 2K 的数中，最优配对方式为第 1 小的数匹配第 1 大的数、第 2 小的数匹配第 2 大的数、\cdots、第 K 小的数匹配第 K 大的数。
接下来考虑在全部的 n 个数中如何选 2K 个数（若 K=0，则不需要选任何数）。
当 K=1 时，显然选择 a_1 与 a_n，因为 a_1 = \min\{a_1,a_2,\cdots,a_n\}，a_n = \max\{a_1,a_2,\cdots,a_n\}，显然 (a_n - a_1)^2 最大。
当 K=i（i 为正整数，i > 1） 时，显然在前 i - 1 个最优的情况下选择剩下的最大值与最小值，即在前 i - 1 个的基础上在选取 a_i 与 a_{n - i + 1}。
所以，应选取 a_1,a_2,\cdots,a_K,a_{n - K + 1},a_{n - K + 2},\cdots,a_n，作为 2K 个元素。也就是第 1 小的数匹配第 1 大的数、第 2 小的数匹配第 2 大的数、\cdots、第 K 小的数匹配第 K 大的数。

得到了上面的结论，a_1,a_2,\cdots,a_n 的 SPD 值就好求了。
首先，对 a_1,a_2,\cdots,a_n 进行排序，然后依次匹配并求出每对数的差的平方的和。
排序的时间复杂度为 \Omicron(n \log_2 n)，匹配的时间复杂度为 \Omicron(n)，所以总的时间复杂度就是 \Omicron(n \log_2 n)。

原题思路

一、暴力

既然题目要求分段，那就暴力进行分段，将计数器赋值为 0，外循环枚举左端点，内循环从左端点开始枚举右端点，每次再按照上面方法计算 SPD 值（不能用原数组排序），如果大于 k，就把左端点到右端点减一的部分作为一段并将左端点赋值为此时的右端点，计数器加一。循环完后，再将计数器加一（最后一段），答案就是最后计数器中的值。
那么，时间复杂度呢？首先，外面的两层循环的时间复杂度是 \Omicron(n) 的；里面的操作（求 SPD 值）是 \Omicron(n \log_2 n) 级的。所以，最终的时间复杂度为 \Omicron(n^2 \log_2 n)，过不了。
但是我们发现，每次会重复对一段进行排序，所以如果每次该用插入排序，在有序的序列中插入一个数的话，时间复杂度可以优化成 \Omicron(n^2)，仍然过不了。

二、二分

注意到固定左端点后，右端点（区间长度）具有单调性。所以，每次可以尝试使用二分右端点（区间长度），而不是直接枚举，可是最坏情况下，可能执行 n 次二分，每次二分最多执行 \log_2 n 次判断函数，每个判断函数的时间复杂度是 \Omicron(n \log_2 n) 级的。
注意到：

\begin{aligned} \sum_{i=0}^{\log_2 n} (\frac{n}{2^i} \log_2 \frac{n}{2^i}) &\le \sum_{i=0}^{\log_2 n} (\frac{n}{2^i} \log_2 n) \\ &\le (\log_2 n) \cdot \sum_{i=0}^{\log_2 n} \frac{n}{2^i} \\ &\le (\log_2 n) \cdot 2n \\ &= 2 \cdot (n \log_2 n)\tag{1} \end{aligned}

所以每次二分的时间复杂度是 \Omicron(n \log_2 n) 级的，然后可以推断出总的时间复杂度是 \Omicron(n^2 \log_2 n)，和朴素版暴力一样，还没有优化版暴力好。那该如何优化呢？
在这里说句题外话：虽然优化之后反倒没有原来的时间复杂度好了，但是也是一种思路，有的时候就是这种看似没用思路优化后成为了时间复杂度更优的算法。

三、倍增

我们发现，二分之所以慢，是因为它的枚举方向，所以可以用倍增替代掉二分。我们发现，可以将二分右端点的部分改成：先从小往大尝试将后面二的幂个元素加入备选序列，直到原序列中元素不足这么多个或者加入备选序列后的 SPD 值大于 k。然后再从最后的加入备选序列的数量开始从大往小尝试将后面二的幂个元素加入备选序列，每次尝试时，如果加入后的备选序列的 SPD 值不大于 k，则加入备选序列；否则，即加入后的备选序列的 SPD 值大于 k，则不加入备选序列。其它的就跟二分的过程差不多了。
时间复杂度：外层一样的 \Omicron(n)，内层每次倍增最多排序 2 \log_2 n 次（常数忽略不计）。由 (1)，时间复杂度为 \Omicron(n^2 \log_2 n)，与二分一样。

四、倍增 + 归并

在上面倍增的思路中，我们发现每次倍增中进行的排序的序列左端点都是重合的，只是右边延伸了一段。所以可以想到，将原来直接排序的部分修改成：先将加入备选序列的部分排好序（当然不能存在原数组中），然后用归并（双指针）的方式将两个有序序列合并成一个大的有序序列。
时间复杂度：外层还是 \Omicron(n)，内层每次倍增最多归并 2 \log_2 n 次（常数忽略不计）。那每次倍增的复杂度是 \Omicron(n \log_2 n)，总的时间复杂度是否还是 \Omicron(n^2 \log_2 n) 呢？不是。我们发现，每一段只会被排一次序。所以，总的排序操作的时间复杂度的和应该不超过 \Omicron(n \log_2 n)。而归并的时间复杂度的和也不超过 \Omicron(n \log_2 n)。所以总的时间复杂度就是 \Omicron(n \log_2 n)。通过！
不过，归并完后的时候可以将结果复制回原数组（如果结果的 SPD 值不大于 k 的话）。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T& r) {
    r=0;bool w=0; char ch=getchar();
    while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
    while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
    r=w?-r:r;
}
int T, n, m, k, ii, ans, p[500010], a[500010], b[500010];
bool check(int l, int r, int rr) {
    if(rr > n) return false;
    int p1 = l, p2 = r + 1, p3 = l, s = 0;
    for(int i = l; i <= rr; i ++) {
        a[i] = p[i];
    }
    sort(a + r + 1, a + rr + 1);
    while(p1 <= r && p2 <= rr) {
        if(a[p1] < a[p2]) b[p3++] = a[p1++];
        else b[p3++] = a[p2++];
    }
    while(p1 <= r) b[p3++] = a[p1++];
    while(p2 <= rr) b[p3++] = a[p2++];
    for(int i = l, j = rr, o = 1; i < j && o <= m; i ++, j --, o ++) {
        s += ((b[j] - b[i]) * (b[j] - b[i]));
        if(s > k) return false;
    }
    for(int i = l; i <= rr; i ++) {
        p[i] = b[i];
    }
    return true;
}
signed main()
{
    read(T);
    while(T --) {
        read(n);read(m);read(k);
        for(int i = 1; i <= n; i ++) {
            read(p[i]);
        }
        ans = 0;
        for(int l = 1, r = 0; l <= n; ++ans) {
            for(ii = 1; check(l, r, r + ii); ii <<= 1) {
                r += ii;
            }
            ii >>= 1;
            for(; ii; ii >>= 1) {
                if(check(l, r, r + ii)) {
                    r += ii;
                }
            }
            l = r + 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

提交记录

我的提交记录

最后说的话

本题的代码虽然略微有一点儿长，但是还是要自己手打，千万不可以抄代码。
最后祝愿大家 AC！