题干

小朋友拍照:有来自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

上一题 下一题 0.0难度 选择题 更新时间:2019-08-24 09:57:56

答案(点此获取答案解析)

①处改为m + 1;②处改为t + f (j)

同类题3

阅读理解

    Today, many people use plants from other places to design their yards. Well, do they have any influence on animals living nearby? As we know, plants supply food for things like insects and plant-eating animals. In turn, birds and meat-eating animals feed on these insects and plant-eating animals. It is easy to see how important plants are.

    Although foreign plants may look beautiful, they can cause problems when there are too many of them. I live in Virginia, USA, and sometimes see a plant—commonly known as Kudzu—that seems to cover everything in the area, even climbing over whole trees and houses.

    Kudzu is an unbelievable plant since it grows very fast. It was first brought to the United States from south-east Asia around the 1870's as a crop that farmers could grow. However, Kudzu quickly came to be considered harmful throughout the southern United States.

    Since Kudzu grows fast in many different environments, it can completely cover areas of land quickly. The plant is also not eaten by any insects or birds in the United States so it can grow unchecked. Kudzu can cover trees, bushes, and even houses. It costs the United States 500 million dollars a year to just keep Kudzu from growing too fast. The plant is a perfect example of what scientists call an invasive (侵略性的) species, which grows more quickly than other native plants.

    All foreign plants have the possibility to spread quickly. Not only are they costly, but planting them in gardens actually takes away food from insects. If everyone filled their garden with plants native to where they live, many lovely butterflies and other native creatures would be attracted to their backyards! So, take a look out of your window — how does your garden grow?