题解：P10455 Genius Acm

Kaf_yoU · 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。

则有两种取数方式：

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

两式相减，得：

由于 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;
}

写在最后

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

谢谢观看！