小朋友拍照:有来自K(1<=K<=20)个不同国家的N(1<=N<=100)个小朋友排成一行准备拍照。国籍用数字1,2,3……K表示,每个小朋友的国籍依次存入数组a(1)到a(N)。由于小朋友太多,没有办法全部被拍入。摄像师决定拍摄一段连续区间内的小朋友,这个区间内每种国籍的小朋友至少要有1个,求满足要求的最小区间长度。 例如有10个小朋友,5种国籍,从左到右排列,国籍编号依次是2,1,2,4,3,3,5,5,3,5,则最小的一段包含所有5种国籍的区间是从第2个到第7个小朋友,区间长度为6。
算法解析:区间的长度至少为K(国籍的数量),最大为N(小朋友的数量)。我们可以通过二分K到N之间的求得最小区间长度。
实现上述功能的VB代码如下,但加框处代码有错,请改正。
Dim a(1 To 100) As Integer '依次存储为1到100的小朋友的国籍编号
Dim K As Integer
Dim N As Integer
Private Sub Form_Load() '窗体加载,生成数据
'产生N的值,表示人数
'产生K的值,表示国籍种数
'产生编号为1到N的小朋友的国籍编号,并存储在数组a中
'代码略
End Sub
Private Sub Command1_Click() '使用二分的思想计算最小区间
Dim M As Integer
i = K: j = N '答案的范围为K到N,即最少K,最多N个小朋友
Do While i <= j
M = (i + j) \ 2 '二分,求中间值
If pd(M) = True Then '调用Pd函数,判断区间长度为M时,是否包含所有国籍
j = M – 1
ans = M '若以M为区间长度可包含所有国籍,更新答案
Else
i = '第①处错误
End If
Loop
Text1.Text = Str(ans)
End Sub
Function pd(M As Integer) As Boolean
Dim f(1 To 20) As Integer 'f(i)表示国籍为i的小朋友是否包含
Dim t As Integer 't用于统计当前区间包含的国籍数量
pd = False
For i = 1 To N - M + 1 '枚举以i为起点的M个小朋友中,各个国籍是否包含
For j = i To i + M - 1
f(a(j)) = 1 '等于1,表示国籍为a(j)的小朋友已包含,0表示不包含
Next j
t = 0
For j = 1 To K '统计已包含的国籍的数量
t = '第②处错误
Next j
If t = K Then pd = True: Exit Function '若包含K个国籍,返回True
For j = 1 To K 'f数组元素重新初始化为0
f(j) = 0
Next j
Next i
End Function