AcWing 109. 天才ACM【倍增+归并】

逃离我推掉我的手 2023-05-29 11:50 19阅读 0赞

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

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

现在给定一个长度为 NN 的数列 AA 以及一个整数 TT。

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

求最少需要分成几段。

输入格式

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

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

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

输出格式

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

数据范围

1≤K≤121≤K≤12,  
1≤N,M≤5000001≤N,M≤500000,  
0≤T≤10180≤T≤1018,  
0≤Ai≤220

思路：首先计算的话肯定是需要每次贪心的取最大最小然后计算，但在考虑区间的时候枚举显然是不行的，所以我们需要考虑倍增来写，每次判断能否扩展。由于取最大最小需要有序，我们每次保存之前的左区间，然后对右区间进行排序，利用归并的思想将有序的左右区间合成一个有序区间，然后就可以进行判断了。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 5e5 + 10;
    const ll linf = 0x3f3f3f3f3f3f3f3f;
    ll a[maxn], b[maxn], v[maxn];
    int n, m, k;
    ll T;
    
    void Merge(int l, int mid ,int r) 
    {
        int i = l, j = mid + 1;
        k = 0;
        while(i <= mid && j <= r)
        {
            if(a[i] <= a[j])
                b[++k] = a[i++];
            else
                b[++k] = a[j++];
        }
        while(i <= mid) b[++k] = a[i++];
        while(j <= r) b[++k] = a[j++];
    }
    bool check(int l, int mid, int r) // 判断区间是否可扩展
    {
        for(int i = mid + 1 ; i <= r; ++i) a[i] = v[i];
        sort(a + mid + 1, a + r + 1); //由于左区间有序所以只需对右区间排序就行了
        Merge(l, mid, r); //归并为一个有序数组
        ll ret = 0;
        int L = 1, R = k, cnt = 0;
        while(L <= R && cnt < m) //取出m对计算答案
        {
            ret += (b[L] - b[R]) * (b[L] - b[R]);
            ++L, --R, ++cnt;
        }
        if(ret <= T)
        {
            k = 0; //如果可以扩展就将右区间拷贝下来
            for(int i = l; i <= r; ++i) a[i] = b[++k];
            return true;
        }
        return false;
    }
    
    int main()
    {
        int t;
        scanf("%d", &t);
        while(t--)
        {
            scanf("%d%d%lld", &n, &m, &T);
            for(int i = 1; i <= n; ++i) scanf("%lld", &v[i]);
            int l = 1, r = 1, len = 1, tot = 0;
            a[1] = v[1];
            while(r <= n)
            {
                if(len == 0) //当前区间结束
                {
                    len = 1;
                    ++tot, ++r;
                    l = r;
                    a[l] = v[l];
                }
                else if(r + len <= n && check(l, r, r + len))
                {
                    r += len;
                    len <<= 1; //倍增
                    if(r == n) break;
                }
                else len >>= 1;
            }
            if(r == n) ++tot;
            printf("%d\n", tot);
        }
        return 0;
    }