3321 问题 C: 蓝桥杯2025年第十六届省赛真题-画展布置

 时间限制: 1s 内存限制: 256MB
题目描述

画展策展人小蓝和助理小桥为即将举办的画展准备了 N 幅画作,其艺术价 值分别为 A1, A2, . . . , AN。他们需要从这 N 幅画中挑选 M 幅,并按照一定顺序 布置在展厅的 M 个位置上。如果随意挑选和排列,艺术价值的变化可能会过于 突兀,导致观众的观展体验不够流畅。 

为了优化布置,他们查阅了《画展布置指南》。指南指出,理想的画展应使 观众在欣赏画作时,艺术价值的过渡尽量平缓。指南建议,选择并排列 M 幅 画,应使艺术价值的变化程度通过一个数值 L 来衡量,且该值越小越好。数值 L 的定义为:

                                                             画展布置

其中 Bi 表示展厅第 i 个位置上画作的艺术价值。 

现在,他们希望通过精心挑选和排列这 M 幅画作,使 L 达到最小值,以提升画展的整体协调性。请你帮他们计算出这个最小值是多少。

输入

输入共两行。 

第一行包含两个正整数 N 和 M,

分别表示画作的总数和需要挑选的画作数量。 

第二行包含 N 个正整数 A1, A2, . . . , AN,表示每幅画作的艺术价值。

输出

输出一个整数,表示 L 的最小值。

样例输入

4 2
1 5 2 4

样例输出

3
提示

【评测用例规模与约定】 

对于 40% 的评测用例,2 ≤ M ≤ N ≤ 103,1 ≤ Ai ≤ 103。 

对于 100% 的评测用例,2 ≤ M ≤ N ≤ 105,1 ≤ Ai ≤ 105

比赛公告

这是2025年第十六届蓝桥杯大赛软件赛省赛C/C++大学B组真题的编程题,填空题在下。大家使用自己的语言做题,可以看到其他人的排名。这次一天之内完成,后续会进行限时训练。

【选手须知】 

考试开始后,选手首先下载题目,并使用考场现场公布的解压密码解压试题。 

考试时间为 4 小时。考试期间选手可浏览自己已经提交的答案,被浏览的答案允许拷贝。

时间截止后,将无法继续提交或浏览答案。 

对同一题目,选手可多次提交答案,以最后一次提交的答案为准。 

选手必须通过浏览器方式提交自己的答案。

选手在其它位置的作答或其它 方式提交的答案无效。 

试题包含“结果填空”和“程序设计”两种题型。 

结果填空题:要求选手根据题目描述直接填写结果。求解方式不限。不要求源代码。把结果填空的答案直接通过网页提交即可,不要书写多余的内容。 

程序设计题:要求选手设计的程序对于给定的输入能给出正确的输出结果。 考生的程序只有能运行出正确结果才有机会得分。 

注意:在评卷时使用的输入数据与试卷中给出的示例数据可能是不同的。 选手的程序必须是通用的,不能只对试卷中给定的数据有效。 

对于编程题目,要求选手给出的解答完全符合 GNU C/C++ 标准,不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的 API。 

代码中允许使用 STL 类库。 

注意: main 函数结束必须返回 0。 

注意: 所有依赖的函数必须明确地在源文件中 #include

所有源码必须在同一文件中。调试通过后,拷贝提交。 

提交时,注意选择所期望的编译器类型。

试题 A: 移动距离 (本题总分:5 分) 

【问题描述】 

小明初始在二维平面的原点,他想前往坐标 (233, 666)。在移动过程中,他 只能采用以下两种移动方式,并且这两种移动方式可以交替、不限次数地使用:

 1. 水平向右移动,即沿着 x 轴正方向移动一定的距离。 

2. 沿着一个圆心在原点 (0, 0)、以他当前位置到原点的距离为半径的圆的圆 周移动,移动方向不限(即顺时针或逆时针移动不限)。 

在这种条件下,他到达目的地最少移动多少单位距离? 

你只需要输出答案四舍五入到整数的结果。 

【答案提交】 

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一 个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。


试题 B: 客流量上限 (本题总分:5 分) 

【问题描述】 

一家连锁旅馆在全国拥有 2025 个分店,分别编号为 1 至 2025。随着节日 临近,总部决定为每家分店设定每日客流量的上限,分别记作 A1, A2, . . . , A2025。 这些上限并非随意分配,而是需要满足以下约束条件: 

1.A1, A2, . . . , A2025 必须是 1 至 2025 的一个排列,即每个 Ai 均是 1 至 2025 之间的整数,且所有 Ai 互不相同。

2. 对于任意分店 i 和 j(1 ≤ i, j ≤ 2025,i 可等于 j),它们的客流量上限 Ai 和 Aj 的乘积不得超过 i × j + 2025。 

这些约束旨在平衡各分店客流压力,确保服务质量和运营稳定性。 

现在,请你计算这样的分配方案究竟有多少种。由于答案可能很大,你只 需输出其对 109 + 7 取余后的结果即可。 

【答案提交】 

这是一道结果填空题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。