S0037. Genius ACM
题意
给定一个整数 \(M\)，对于任意一个整数集合 \(S\)，定义“校验值”如下:
从集合 \(S\) 中取出 \(M\) 对数(即 \(2 \times M\) 个数，不能重复使用集合中的数（如果 \(S\) 中的整数不够 \(M\) 对，则取到不能取为止），使得“每对数的差的平方”之和最大，这个最大值就称为集合 \(S\) 的“校验值”。
现在给定一个长度为 \(N\) 的数列 \(A\) 以及一个整数 \(T\)。我们要把 \(A\) 分成若干段，使得每一段的“校验值”都不超过 \(T\)。求最少需要分成几段。
思路
贪心
假设现在只有四个数 \(a\)，\(b\)，\(c\)，\(d\)（\(a \le b \le c \le d\)）。
则有三种情况：
- \(a\) 和 \(b\) 一组，其余一组（因为递增，所以一定非最优）。
- \(a\) 和 \(c\) 一组，其余一组。
- \(a\) 和 \(d\) 一组，其余一组。
后两组”每对数的差的平方之和“的差为：
LaTex好难用
于是我们发现，\((b - a) > 0\)，\((c - d) < 0\)！
也就是说，\(a\) 和 \(d\) 一组一定优于 \(a\) 和 \(c\) 一组。
同理可得，我们要将最大的 \(A_i\) 和最小的 \(A_i\) 配对，次大的 \(A_i\) 和次小的 \(A_i\) 配对，以此类推。
倍增
我们发现二分有一点浪费了，所以我们很容易想到倍增。
由于右端点可能只移一小段，但二分却直接移了一大段，十分浪费。
步骤：
- 新建倍增变量 \(bz\) 和当前的左右端点 \(L\) 和 \(R\)。
- 求出 \(L\) 到 \(R + bz\) 这一段的校验值 \(k\)，若 \(k \le T\)，则 \(R = r + bz\)，\(bz = 2bz\)，否则 \(bz = \cfrac{bz}{2}\)。
- 重复第二步，直到 \(bz \lt 0\)，此时 \(R\) 为 \(L\) 对应的最优右端点。
时间复杂度是高贵的 \(\mathcal{O}(n\log ^ 2 n)\)，似乎过不了？
我们还可以优化。
归并排序
其实只是归并排序的思想
在归并排序中，我们添加三个参数 \(l, mid, r\)，分别是刚刚的 \(L, R, R + bz\)，此时由于上一次处理时 \(l\) 到 \(mid\) 已经排了序了，所以我们只用排 \(mid\) 到 \(r\) 归并，然后利用归并排序的思想，把 \(l\) 到 \(mid\) 和 \(mid\) 到 \(r\) 归并最后判断答案是否满足 \(ans \le T\)
时间复杂度
\(\mathcal{O}(n \log n)\)
代码
#include <bits/stdc++.h>
#define int long long
#define itn int
#define fro for
using namespace std;
const int N = 5e5 + 10;
int t;
int n, m, k, p[N];
int a[N], b[N];
bool ms(int l, int mid, int r){//归并排序for(int i = mid; i < r; i++){a[i] = p[i];}sort(a + mid, a + r);int nl = l, nr = mid, cnt = 0, ans = 0;while(nl < mid && nr < r){if(a[nl] <= a[nr]) b[cnt++] = a[nl++];else b[cnt++] = a[nr++];}while(nl < mid) b[cnt++] = a[nl++];while(nr < r) b[cnt++] = a[nr++];for(int i = 0; i < m && i < cnt; i++, cnt--){//处理答案ans += (b[i] - b[cnt - 1]) * (b[i] - b[cnt - 1]);}return ans <= k;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> t;while(t--){cin >> n >> m >> k;for(itn i = 0; i < n; i++){cin >> p[i];}int s = 0, e = 0;//L和Rint cnt = 0;while(e < n){int bz = 1;while(bz > 0){//倍增if(e + bz <= n && ms(s, e, e + bz)){e += bz;bz <<= 1;if(e >= n) break;for(int i = s; i < e + bz; i++){a[i] = b[i - s];}}else bz >>= 1;}cnt++;s = e;}cout << cnt << '\n';}}