当前位置: 首页 > news >正文

蓝桥杯 2025 省 B 题:画展布置 - 题解笔记

蓝桥杯 2025 省 B 题:画展布置 - 题解笔记.md

一、题目核心信息

1. 问题描述

给定 N 幅画作的艺术价值数组 A,需从其中挑选 M 幅并排列成序列 B(长度为 M),目标是最小化评价指标 LL 的定义为:

\[L = \sum_{i=1}^{M-1} |B_{i+1}^2 - B_i^2| \]

2. 输入输出格式

  • 输入
    1. 第一行:两个正整数 N(画作总数)和 M(需挑选的画作数);
    2. 第二行:N 个正整数 A_1, A_2, ..., A_N(每幅画的艺术价值)。
  • 输出:一个整数,代表 L 的最小值。

3. 数据规模与约定

评测用例 约束条件
40% 用例 \(2 \leq M \leq N \leq 10^3\)\(1 \leq A_i \leq 10^3\)
100% 用例 \(2 \leq M \leq N \leq 10^5\)\(1 \leq A_i \leq 10^5\)

二、关键推导:基于三角不等式简化问题

1. 三角不等式基础

对任意实数 ab,三角不等式的基本形式为:

\[|a + b| \leq |a| + |b| \]

  • 取等号条件ab 同号(或至少其中一个为 0)。

推广到 n 个实数的和:

\[\left| \sum_{k=1}^n a_k \right| \leq \sum_{k=1}^n |a_k| \]

  • 取等号条件:所有非零项 a_k 的符号一致(全正或全负)。

2. 应用三角不等式到 L

L 中的每一项 \(|B_{i+1}^2 - B_i^2|\) 视为 \(|a_i|\),代入推广后的三角不等式:

\[\sum_{i=1}^{M-1} |B_{i+1}^2 - B_i^2| \geq \left| \sum_{i=1}^{M-1} (B_{i+1}^2 - B_i^2) \right| \]

右侧的求和式是望远镜级数(Telescoping Series),展开后中间项会抵消,最终化简为:

\[\sum_{i=1}^{M-1} (B_{i+1}^2 - B_i^2) = B_M^2 - B_1^2 \]

由此得到关键不等式:

\[L \geq |B_M^2 - B_1^2| \]

3. L 取最小值的条件

要使 L 达到最小值(即 \(L = |B_M^2 - B_1^2|\)),需满足三角不等式的取等条件:
所有 \((B_{i+1}^2 - B_i^2)\) 的符号一致 → 序列 \(B_1^2, B_2^2, ..., B_M^2\)单调序列(递增或递减)。

由于 B_i 是正整数(艺术价值为正),\(B_i^2\)B_i 的单调性完全一致,因此:
序列 B 必须按艺术价值单调排列(从小到大或从大到小)

三、优化思路:从“选+排”到“滑动窗口”

1. 固定选组的最优 L

对任意选出的 M 幅画,若按单调顺序排列,则 L 可简化为:

\[L = B_M^2 - B_1^2 \]

(因 B 单调,\(B_M^2 \geq B_1^2\),绝对值可直接去掉)。

2. 最小化 L 的选组策略

问题转化为:从数组 A 中挑选 M 幅画,使“最大值² - 最小值²”最小。

关键结论:最优选组是“排序后连续的 M 个元素”

若将 A 按升序排序为 \(A_1 \leq A_2 \leq \dots \leq A_N\),则:

  • 任意非连续的 M 个元素,其“最大值 - 最小值”的差距,必然大于等于某组连续 M 个元素的差距。
  • 例:选 \(A_1, A_3, A_4\)M=3),最大值为 \(A_4\),最小值为 \(A_1\),差距为 \(A_4^2 - A_1^2\);而连续组 \(A_2, A_3, A_4\) 的差距为 \(A_4^2 - A_2^2\),显然更小。

四、最终解题步骤

  1. 排序数组:将原始数组 A 按升序排序(时间复杂度 \(O(N \log N)\),适配 \(10^5\) 规模数据)。
  2. 滑动窗口计算:用长度为 M 的窗口遍历排序后的数组,对每个窗口计算 \(A[i+M-1]^2 - A[i]^2\)(时间复杂度 \(O(N)\))。
    • 窗口范围:i\(0\)\(N-M\)(假设数组下标从 0 开始),每个窗口对应 \(A[i]\)\(A[i+M-1]\)M 个元素。
  3. 取最小值:遍历所有窗口计算结果,其中最小的值即为 L 的最小值。

五、示例验证(输入 #1)

输入

4 2
1 5 2 4

解题过程

  1. 排序数组:将 A 排序为 \([1, 2, 4, 5]\)(下标 0-3)。
  2. 滑动窗口计算M=2,窗口数 \(4-2+1=3\)):
    • 窗口 1(i=0,元素 \(1,2\)):\(2^2 - 1^2 = 4 - 1 = 3\)
    • 窗口 2(i=1,元素 \(2,4\)):\(4^2 - 2^2 = 16 - 4 = 12\)
    • 窗口 3(i=2,元素 \(4,5\)):\(5^2 - 4^2 = 25 - 16 = 9\)
  3. 取最小值:结果为 3,与预期输出一致。

六、算法复杂度分析

复杂度类型 具体值 说明
时间复杂度 \(O(N \log N)\) 排序占主导(\(O(N \log N)\)),滑动窗口仅需 \(O(N)\),两者叠加后取高阶项
空间复杂度 \(O(1)\)(或 \(O(N)\) 若原地排序(如快速排序),空间复杂度为 \(O(1)\);若使用非原地排序(如 Python 的 sorted()),空间复杂度为 \(O(N)\),均适配 \(10^5\) 规模

七、代码实现(Python 示例)

# 读取输入
n, m = map(int, input().split())
a = list(map(int, input().split()))# 步骤1:排序数组(升序)
a.sort()# 步骤2:滑动窗口计算最小L值
min_l = float('inf')
# 窗口左边界i的范围:从0到n-m(闭区间)
for i in range(n - m + 1):# 窗口内最小值:a[i],最大值:a[i+m-1](因数组已排序)max_val = a[i + m - 1]min_val = a[i]# 计算当前窗口的L值:max² - min²current_l = max_val ** 2 - min_val ** 2# 更新最小值if current_l < min_l:min_l = current_l# 输出结果
print(min_l)

代码说明

  • 排序:使用 Python 内置 sorted() 函数,时间复杂度 \(O(N \log N)\),稳定性满足需求,且适配 \(10^5\) 规模数据。
  • 滑动窗口:循环范围 range(n - m + 1) 确保窗口不越界(覆盖所有合法的 M 元素组合),每个窗口计算仅需 \(O(1)\) 时间,整体线性效率。
  • 数值计算:直接用 **2 计算平方,避免浮点误差(因 A_i 为正整数,平方结果仍为整数)。
http://www.hskmm.com/?act=detail&tid=17326

相关文章:

  • 二维坐标下的运算
  • Polar2025秋季个人挑战赛web-writeup
  • Day4
  • 题解:P12751 [POI 2017 R2] 集装箱 Shipping containers
  • 弱网配置
  • 绘制金融集团监控大屏的地图demo
  • 实用指南:《原神助手》开源神器:游戏体验大升级
  • 9-25
  • AT_agc021_d [AGC021D] Reversed LCS
  • adb shell 常用文件命令
  • Java文件编程
  • 自我介绍与规划
  • 软件工程学习日志2025.9.25
  • 从50ms到30ms:YOLOv10部署中图像预处理的性能优化实践 - 实践
  • redis实现分布式锁1
  • 完整教程:(13)GPS/无GPS转换
  • Transformer自回归关键技术:掩码注意力原理与PyTorch完整实现
  • 第四篇
  • PyTorch图神经网络(六)
  • Qwen多模态系列模型笔记—Qwen-VL
  • go 语法里变量前面增加、*区别
  • 历程回顾-(2024-2025)
  • CF Round 1053(2150 2151) 总结
  • 20250922_QQ_backdoor
  • 实用指南:【Java八股文】13-中间件面试篇
  • AT_agc012_d [AGC012D] Colorful Balls
  • 02、Python从入门到癫狂:函数与资料容器
  • 第二周第四天2.4
  • 9/25
  • 关闭Edge浏览器页面的圆角效果