AcWing-109-天才ACM

问题

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

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

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

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

求最少需要分成几段。

输入格式

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

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

第二行包含 N 个整数，表示数列A1,A2…AN。

输出格式

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

数据范围

1≤K≤12,
1≤N,M≤500000,
0≤T≤$10^{18}$,
0≤Ai≤$2^{20}$

输入样例：

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

输出样例：

2
1

思路

思路一

同 前缀和的最大k 类似，目标是：当确定左端点后L后，右端点R在满足 A[L] - A[R]的效验值不超过 T 的前提下，最大能取多少。

可采用倍增的思路：

1. 初始化 p = 1， R = L = 1, cnt = 0
2. 求出 [L, R+p] （需判断 R + p 是否大于 n，若大于 p/=2重新执行此步，否则继续执行后面的效验值计算）这一段区间的效验值（使用快速排序），若效验值 <= T，则 R += p, p *= 2，否则 p/ = 2
3. 重复上一步，知道 p = 0，此时 R 即为答案，cnt++，
4. 当上一步得到的 R < n 时，令 p = 1，R++，L = R，继续执行第二步，否则，结束循环，cnt 即为随后分成的几段的值。

思路二 — 优化

将思路一中的计算区间效验值的算法改为归并排序，每次只对[r+1，r+p]区间进行排序，再将[l， r]与[r+1, r+p]区间使用归并排序的merge函数进行合并。

题解

题解一

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;
typedef long long ll;
const int MAX = 5e5 + 5;
int k, n, m;
ll t;
int a[MAX];
int b[MAX];

int solve() {
    int res = 0;

    memcpy(b, a, sizeof(a));
    int l = 1, r = 1, p = 1;
    while (r <= n) {
        if (r + p > n) {
            p >>= 1;
            continue;
        }
        if (p == 0) {
            res++;
            r++;
            l = r;
            p = 1;
            continue;
        }

        for (int j = l; j <= r + p; ++j) a[j] = b[j];
        sort(a + l, a + r + p + 1);
        ll ans = 0;
        int i = 0, end = min(m, r + p - l + 1 >> 1);
        while (i < end) {
            ans += pow(a[r + p - i] - a[l + i], 2);
            i++;
        }

        if (ans <= t) {
            r += p;
            p <<= 1;
        } else p >>= 1;
    }

    return res;
}

int main() {
    cin >> k;
    while (k--) {
        cin >> n >> m >> t;
        for (int i = 0; i < n; ++i) scanf("%d", &a[i + 1]);

        cout << solve() << endl;
    }

    return 0;
}

题解二

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;
typedef long long ll;
const int MAX = 5e5 + 5;
int k, n, m;
ll t;
int a[MAX], b[MAX], c[MAX];

void merge(int l, int mid, int r) {
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (b[i] <= b[j]) c[k++] = b[i++];
        else c[k++] = b[j++];
    }
    while (i <= mid) c[k++] = b[i++];
    while (j <= r) c[k++] = b[j++];

    for (int p = l; p <= r; ++p) b[p] = c[p];
}

void merge_sort(int l, int r) {
    if (l >= r) return;
    if (l + 1 == r) {
        if (b[l] > b[r]) swap(b[l], b[r]);
        return;
    }

    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    merge(l, mid, r);
}

int solve() {
    int res = 0;

    int l = 1, r = 1, p = 1;
    while (r <= n) {
        if (r + p > n) {
            p >>= 1;
            continue;
        }
        if (p == 0) {
            res++;
            r++;
            l = r;
            p = 1;
            continue;
        }

        for (int j = l; j <= r + p; ++j) b[j] = a[j];
        merge_sort(r + 1, r + p);   //归并排序
        merge(l, r, r + p);
        ll ans = 0;
        int i = 0, end = min(m, r + p - l + 1 >> 1);
        while (i < end) {
            ans += pow(b[r + p - i] - b[l + i], 2);
            i++;
        }

        if (ans <= t) {
            for (int j = l; j <= r + p; ++j) a[j] = b[j];
            r += p;
            p <<= 1;
        } else p >>= 1;
    }

    return res;
}

int main() {
    cin >> k;
    while (k--) {
        cin >> n >> m >> t;
        for (int i = 0; i < n; ++i) scanf("%d", &a[i + 1]);
        cout << solve() << endl;
    }

    return 0;
}