首页 > 试题广场 >

画展布置

[编程题]画展布置

热度指数：143 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 展厅共有 $N$ 幅画作，其艺术价值为整数 $A_1,A_2,\dots ,A_N$ 。策展人需选出其中 $M$ 幅依次摆放。设选出后排成一列的价值为 $B_1,\dots ,B_M$ ，定义一个画展的不和谐度 $L$ 满足：

$L\;=\;\sum_{i=1}^{M-1}\bigl|B_{i+1}^2-B_i^2\bigr|.$

$\hspace{15pt}$ 请最小化 $L$ 并输出其最小可能值。

输入描述:

第一行输入两个整数 。 
第二行输入  个整数 。

输出描述:

输出一个整数，表示最小化后的  值。

示例1

输入

4 2
1 5 2 4

输出

说明

选择  得到 ，为最小值。

算法知识视频讲解

Python3

牛客647428429号

n, m = map(int, input().split())
a = list(map(int, input().split()))
a,min1 = sorted(a), float('inf')
for i in range(n-m+1):
    x,y = a[i],a[i+m-1]
    shu = y**2-x**2
    if shu < min1:
        min1 = shu
print(min1)

##此题看似很难，但是我们在做这种题的时候，都一定是转化为单循环，双循环必超时，由于不和谐度与数之间的差值和和有关，因为x平方减y平方等于x与y的和乘以x与y的差，所以xy应该尽量小，且差值也应该小，所以此时可以直接sorted，之后可以发现，因为排序后Bi的值一直在增大，所以可以去掉绝对值，所以化简成了最后一个数的平方减去第一个数的平方，由此转化成了单循环

发表于今天 09:46:42 回复(0)