文章目录

• • @[toc]
  • 一、题目
  • • 1、题目描述
    • 2、输入输出
    • • 2.1输入
      • 2.2输出
    • 3、原题链接
  • 二、解题报告
  • • 1、思路分析
    • 2、复杂度
    • 3、代码详解

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

https://www.luogu.com.cn/problem/P10455

二、解题报告

1、思路分析

先考虑这样一个问题，2n个数配成n个pair (xi, yi) 令 ${\sum }_{i=0}^{n-1}(x_i-y_i{)}^2$ 最小，怎么做？
$$\sum _{i=0}^{n-1}(x_i-y_i{)}^2=\sum _{i=0}^{2n-1}{a}_i^2-2\sum _{i=0}^{n-1}{x}_i{y}_i$$
因为第一项是常数，问题变成了最小化pair的乘积和
这个是经典贪心，顺序积之和 > 乱序积之和 > 逆序积之和
现在可以确定一个连续段如何求其最大SPD，那么就有暴力做法：
固定左端点l，然后不断往右尝试加入新元素，一旦加入新元素无法满足SPD <= k，那么再开一个段
这样做的复杂度是O(N^2)的，因为我们要维护一个有序数组，每次暴力插入O(N)，求SPD O(N)，扩展N次
如何加速扩展操作？
二进制倍增扩展，设当前扩展长度为b，每次尝试往后新加入b个元素，然后求SPD，成功就将b * 2，否则b / 2，并且恢复数组
由于b 会遍历 1,2,…2^{logn}，所以每个分组的长度一定会被凑出来
这样扩展每组的扩展次数降低到了log次
一个常数级优化：每次只需对扩展部分排序，然后和当前序列做归并

2、复杂度

时间复杂度： O(Nlog^2 N) 空间复杂度：O(N)

3、代码详解

#include <bits/stdc++.h>
namespace ranges = std::ranges;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;

void solve() {
    int n, m;
    i64 k;
    std::cin >> n >> m >> k;
    std::vector<int> P(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> P[i];
    }

    int ans = 0;
    std::vector<int> t, a, na;
    for (int i = 0; i < n; ) {
        a.clear();
        int b = 1;
        while (b > 0) {
            if (i + b > n) {
                b /= 2;
                continue;
            }
            t.clear();
            na.clear();
            t.insert(t.end(), P.begin() + i, P.begin() + i + b);
            ranges::sort(t);
            std::merge(a.begin(), a.end(), t.begin(), t.end(), std::back_inserter(na));
            i64 cost = 0;
            for (int l = 0, r = na.size() - 1, c = 0; c < m && l < r; ++l, --r, ++c) {
                i64 d = na[r] - na[l];
                cost += d * d;
            }
            if (cost <= k) {
                i += b;
                a.swap(na);
                b *= 2;
            } else {
                b /= 2;
            } 
        }
        ++ans;
    }
    std::cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T;
    std::cin >> T;
    while(T-- > 0) {
        solve();
    }

    return 0;
}