如何有效地解决这个问题?

问题描述 投票:-1回答:1

有n个装有Ai球的盒子。有M种颜色,并且该盒子已经涂有M种颜色,因此相邻的盒子具有不同的颜色。任务是选择那些M个盒子,以使所选择的盒子中没有两个具有相同的颜色,并且所选择的盒子中最大和最小球数之间的差异最小。

例如:4(N)2(中)10 20 15 28 =每个框中的球的值。输出:5如何解决这个问题?任何有效的解决方案?限制条件:2 <= M <= N <= 10 ^ 5

python c++ algorithm math
1个回答
0
投票

解决方案很明显,它的O(m)

这里是算法,

INPUT n,m,A
DECLARE right=m-1,left=0,minSum=9999999
WHILE right < n:
    IF minSum > A[right]-A[left]:
        minSum = A[right]-A[left]
    right+=1
    left+=1
OUTPUT minSum
© www.soinside.com 2019 - 2024. All rights reserved.