有n个装有Ai球的盒子。有M种颜色,并且该盒子已经涂有M种颜色,因此相邻的盒子具有不同的颜色。任务是选择那些M个盒子,以使所选择的盒子中没有两个具有相同的颜色,并且所选择的盒子中最大和最小球数之间的差异最小。
例如:4(N)2(中)10 20 15 28 =每个框中的球的值。输出:5如何解决这个问题?任何有效的解决方案?限制条件:2 <= M <= N <= 10 ^ 5
解决方案很明显,它的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