自动搬运

查看原文

来自洛谷，原作者为

	DDD_et 「初始之音响彻未来」 || miku + kafu + flower 三厨请支持谢谢喵 || 终わりなき爱の随に さあ - 爱や厌 * ∞ || 壶关请说明你一般在犇犇里发什么（

搬运于2025-08-24 22:58:06，当前版本为作者最后更新于2024-12-03 07:07:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P10455 Solution

做法：贪心，倍增，归并思想

题意

给定 $n$ 台 CPU 的性能 $P_1\dots P_n$，问至少要分成几组，才能使在每组里抽取 $\min \{m,\frac{n}{2}\}$ 台 CPU 时使得其 SPD 最大不超过 $k$。

设一组 CPU 的性能为 $d_1 \dots d_n$，则这组 CPU 的 SPD 定义为 $(d_1-d_2)^2+(d_3-d_4)^2+\dots+(d_{n-1}-d_n)^2$。

思路

Part 1. 贪心

第一眼我们知道测试用的 CPU 既然是随机抽，那么我们要使得最大的 SPD 都不超过 $k$，SPD 的最大值当然不能枚举，所以考虑贪心策略。

设有四数 $a,b,c,d$，且它们满足 $a<b<c<d$。

则有两种取数方式：

• $a$ 与 $d$ 一组，剩下的另一组。
• $a$ 与 $c$ 一组，剩下的另一组。

则第一种方式的 SPD 为 $(d-a)^2+(c-b)^2$，第二种方式的 SPD 为 $(c-a)^2+(d-b)^2$。

两式相减，得：

$$\begin{aligned} (d-a)^2+(c-b)^2-(c-a)^2-(d-b)^2 &= (d-a)(d-a)+(c-b)(c-b)-(c-a)(c-a)-(d-b)(d-b) \\ &=(d^2-2ad-a^2)+(c^2-2bc-b^2)-(c^2-2ac-a^2)-(d^2-2bd-b^2) \\ &=2ac+2bd-2ad-2bc \\ &=2(d-c)(b-a) \end{aligned} $$

由于 $d>c,b>a$，所以 $d-c$ 和 $b-a$ 均大于 $0$。

即我们要使题目中最大的 $D_i$ 与最小的 $D_i$ 配对，使第二大的 $D_i$ 与第二小的 $D_i$ 配对，以此类推。

Part 2. 倍增

根据题目数据，肯定是不能二分的，因为最坏情况下需要进行 $n$ 次二分，会使时间复杂度变为 $\mathcal{O}(n^2 \log^2 n)$。

那么可以用倍增平替掉（什么是倍增？）。朴素思想就是倍增模版，用变量 $\text{stt}$ 记录当前的位置，$\text{add}$ 记录平移的元素数，当排序后求出来的 SPD 小于等于 $k$ 时 并将 $\text{add}$ 乘上 $2$，否则 $\text{add}$ 除以 $2$，注意一般采用左闭右开区间。

时间复杂度 $\mathcal{O}(n \log^2n)$。

Part 3. 归并思想优化

归并立大功。

发现在求 SPD 的函数中，每次都要将当前数组排一遍序，时间开销较大，所以考虑使用归并排序的思想。

增加一个变量 $\text{end}$ 记录上次结束时的位置作为中心点，我们既然在上次倍增时已经对 $[\text{stt},\text{end})$ 这个区间排了序，那么这次只要排序 $[\text{end},\text{end}+\text{add})$，并用归并排序的思想将这两个数组合并再求 SPD 即可。

记得在符合条件后更新用来排序的数组并且不管怎样都要更新 $\text{stt}$ 为 $\text{end}$。

时间复杂度 $\mathcal{O}(n \log n)$，可以通过。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
int n, m, k, t, p[N], m1[N], m2[N];

int RPD (int a, int b) { return a - b; }

bool check (int s, int mid, int e)
{
	for (int i = mid; i < e; i ++) m1[i] = p[i];
	sort (m1 + mid, m1 + e); //只排序[mid,e)
	
	int lp = s, rp = mid, idx = 0, res = 0;
	while (lp < mid && rp < e) //归并
	{
		if (m1[lp] <= m1[rp]) m2[idx ++] = m1[lp ++];
		else m2[idx ++] = m1[rp ++];
	}
	while (lp < mid) m2[idx ++] = m1[lp ++];
	while (rp < e) m2[idx ++] = m1[rp ++];
	
	for (int i = 0; i < m && i < idx; i ++, idx --)
		res += pow (RPD (m2[i], m2[idx - 1]), 2); //贪心求 SPD
	return res <= k;
}

signed main ()
{
    scanf ("%lld", &t);
	while (t --)
	{
		scanf ("%lld%lld%lld", &n, &m, &k);
		for (int i = 0; i < n; i ++) scanf ("%lld", p + i);
		int stt = 0, end = 0, cnt = 0;
		while (end < n)
		{
			int add = 1;
			while (add > 0)
			{
				if (end + add <= n && check (stt, end, end + add))
				{
					end += add, add <<= 1;
					if (end >= n) break;
					for (int i = stt; i < end + add; i ++)
						m1[i] = m2[i - stt]; //更新用来排序的数组
				}
				else add >>= 1;
			}
			cnt ++, stt = end; //更新起始位置
		}
		printf ("%lld\n", cnt);
	}
	return 0;
}

写在最后

还是那句话，归并立大功。

谢谢观看！